\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{amsmath}
\usepackage{amsthm}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/
~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf  \Large \bf Two Game-Set Inequalities}

\vskip 1cm
\large
Walter Shur \\
11 Middle Road \\
Port Washington, NY 11050 \\
USA \\
\href{mailto:shur@optonline.net}{\tt shur@optonline.net} \\
\end{center}

\vskip .2 in

\begin{abstract}
Two players compete in a contest where the first player to win  a
specified number of   points wins the  game, and the first player to
win a specified number of games wins the set. This paper proves two
generalized inequalities, each independent of the probability of
winning a point, concerning the better player's chances of winning.
Counterexamples are given for two additional conjectured inequalities.
A sequence of integers which plays a significant role in this paper can
be found in A033820 of the On-line Encyclopedia of Integer Sequences.
\end{abstract}



% \documentclass[amsmath,12pt]{article}
% 
% \usepackage{amsmath}
% \usepackage{amsthm}
% \usepackage{amsbsy}
% 
\newtheorem{theo}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{conjecture}{Conjecture}
% 
% \setlength{\oddsidemargin}{.25 in}
% \setlength{\textwidth}{6 in}
% \setlength{\topmargin}{0 in}
% 
% \begin{document}
% 
% \begin{center}
% \Large \bf Two  Game-Set Inequalities
% \vspace{.2 in}
% 
% \rm Walter Shur
% \vspace{.1 in}
% 
% 11 Middle Road
% 
% Port Washington, NY 11050
% 
% shur\verb @ optonline.net
% 
% \end{center}

%\abstract{ Two players compete in a contest where the first player to
%win  a specified number of   points wins the  game, and the first
%player to win a specified number of games wins the set. This paper
%proves two generalized inequalities, each independent of the
%probability of winning a point, concerning the better player's chances
%of winning. Counterexamples are given for two additional conjectured
%inequalities. A sequence of integers which plays a significant role in
%this paper can be found in A033820 of the On-line Encyclopedia of
%Integer Sequences.}

\section{Introduction}


$A$ and $B$ play a set of games. The winner of each game is the first
player to win $k$ points, and the winner of the set is the first player
to win $n$ games. The probabilities that $A$ and $B$ win each point are
$p$ and $q$, respectively, with \mbox{$p+q=1$}.  Let $P(n,k,p)$ and
$Q(n,k,p)$ be the probabilities that $A$ wins and loses the set,
respectively . Let $P(n,p)=P(n,1,p)=P(1,n,p)$ and
\mbox{$Q(n,p)=Q(n,1,p)=Q(1,n,p)$} be the probabilities that $A$ wins
and loses an $n$ point game, respectively. (Note that
$P(n,k,p)=P(n,P(k,p))$ and $Q(n,k,p)=Q(n,P(k,p))$.  This paper  proves the
following two theorems:

\vspace{.1in}
\begin{theo}
If $n\ge 2,\ k\ge 2,$ and $.5<p<1$, then
$P(n,k,p)>P(nk,p)$.
\end{theo}

\vspace{.1in}

\begin{theo}
If $2 \leq k <n $ and $ .5<p<1$, then
$P(n,k,p)>P(k,n,p)$.
\end{theo}



\section{Proofs}




\begin{lem}
$P(k,p)=\frac{1}{2}+\frac{1}{2}(p-q)\displaystyle\sum_{i=0}^{k-1}\binom{2i}{i}(pq)^i.$
\end{lem}

\begin{proof}

We show first that

\begin{equation}
P(k+1,p)-P(k,p)=\frac{1}{2}(p-q)\binom{2k}{k}(pq)^k, \ k\ge1.     
\end{equation}

The only $(k+1)$-point games in which the winner might be different than the winner of the $k$-point game are those which are tied at $k$ points each. 

The increase in $A$'s chance of winning a $k+1$-point game over his
chance of winning a $k$-point game is the excess of (a) the probability
that there is a $k$-point tie, $B$ having won the $k$-point game, and
$A$ wins the next point, over (b) the probability that there is a
$k$-point tie, $A$ having won the $k$-point game, and $B$ wins the next
point. Note that in half of those tied games, $B$ won the $k$-point
game, and in the other half, $A$ won the $k$-point game. Since
$\binom{2k}{k}(pq)^k$ is the probability of a $k$-point tie, (1)
holds.


Lemma 1 is true since it is  true for $k=1$, and its right hand side
simply sums the differences in (1).

\end{proof}

\begin{lem}
Let $\displaystyle a_{k,i} :=\frac{1}{2}\binom{2k}{k}\binom{2i}{i}\frac{k}{k+i}$.
Then
$P(k,p)Q(k,p)=(pq)^k \displaystyle \sum_{i=0}^{k-1}a_{k,i}(pq)^i$,\\
\end{lem}

(Note that $a_{k,i}$ is equal to  $a_{k+i-1,k-1}$ in A033820 of the
On-line Encyclopedia of Integer Sequences.)

\begin{proof}
We see from Lemma 1, noting that $-(p-q)^2=4pq-1$, that

\begin{equation}
P(k,p)Q(k,p)=\frac{1}{4}+\frac{1}{4}(4pq-1)\left(\sum_{i=0}^{k-1}\binom{2i}{i}(pq)^i\right)^2. 
\end{equation}

Since
\[\left(\sum_{i=0}^\infty
\binom{2i}{i}(pq)^i\right)^2=\left(\frac{1}{\sqrt{1-4pq}}\right)^2=\sum_{i=0}^\infty
4^i(pq)^i,\]
we see that if $1\le t\le k-1$, the coefficient of
$(pq)^t$   in (2) equals \mbox{$\frac{1}{4}\cdot4\cdot
4^{t-1}-\frac{1}{4}\cdot 4^t =0$}, and equals $0$ for $t=0$ as well.
\vspace{.2in}

Hence, we can define $a_{k,i}$ such that

\begin{equation}
P(k,p)Q(k,p)=(pq)^k \sum_{i=0}^{k-1}a_{k,i}(pq)^i.  
\end{equation}

Thus,  $a_{k,t-k}$ is the coefficient of $(pq)^t$ in (2).


\noindent   We have, then



\begin{align*}
a_{k,t-k}&=\sum_{j=t-k}^{k-1}\binom{2j}{j}\binom{2t-2j-2}{t-j-1}-\frac{1}{4}\sum_{j=t-k+1}^{k-1}\binom{2j}{j}\binom{2t-2j}{t-j}\\
&\phantom{=}\\
&=\binom{2t-2k}{t-k}\binom{2k-2}{k-1}+\sum_{j=t-k+1}^{k-1}\binom{2j}{j}\left(\binom{2t-2j-2}{t-j-1}-\frac{1}{4}\binom{2t-2j}{t-j}\right)\\
&\phantom{=}\\
&=\binom{2t-2k}{t-k}\binom{2k-2}{k-1}+\frac{1}{2}\sum_{j=t-k+1}^{k-1}\binom{2j}{j}\binom{2t-2j-2}{t-j-1}\frac{1}{t-j}.\hspace{.4in}(4)
\end{align*}

\[\mbox{Let}\  g(t,j)=\frac{j(2t-2j-1)\binom{2j}{j}\binom{2t-2j-2}{t-j-1}}{(t-j)t}.\]  

\addtocounter{equation}{1}
We show that
\begin{equation}
\binom{2j}{j}\binom{2t-2j-2}{t-j-1}\frac{1}{t-j}=g(t,j+1)-g(t,j) 
\end{equation}
by dividing both sides of the equation by $\binom{2j}{j}\binom{2t-2j-2}{t-j-1}$ to obtain
\[\frac{1}{t-j}=\frac{1+2j}{t}-\frac{j(2t-2j-1)}{(t-j)t}=\frac{1}{t-j}.\]

Let $S(t,k)$ equal the sum in (4). By summing both sides of (5) from \mbox{$j=t-k+1$} to $k-1$,
we see that  $S(t,k)$ is equal to $g(t,k)-g(t,t-k+1)$, and we have
\[S(t,k)=\frac{k(2t-2k-1)\binom{2k}{k}\binom{2t-2k-2}{t-k-1}}{(t-k)t}-\frac{(t-k+1)(2k-3)\binom{2t-2k+2}{t-k+1}\binom{2k-4}{k-2}}{(k-1)t}. \ \]

We see from (4) that
\[a_{k,t-k}=\binom{2t-2k}{t-k}\binom{2k-2}{k-1}+\frac{1}{2}S(t,k).\]
Dividing both sides by $\binom{2k}{k}\binom{2t-2k}{t-k}$, we have
\[\frac{a_{k,t-k}}{\binom{2k}{k}\binom{2t-2k}{t-k}}=\frac{k}{4k-2}+\frac{1}{2}\left(\frac{k}{2t}-\frac{k(2t-2k+1)}{2(2k-1)t}\right)=\frac{k}{2t}.\]
Replacing $t$ by $k+i$ gives
\[a_{k,i}=\frac{1}{2}\binom{2k}{k}\binom{2i}{i}\frac{k}{k+i}.\]

\end{proof}

\begin{lem}

\[P'(k,p)=\frac{1}{2}k\binom{2k}{k}(pq)^{k-1}, \mbox{where the derivative is taken with respect to}\  p.\]
\end{lem}

\begin{proof}
The probability that $A$ wins a $k$-point game on the $(k+i)^{th}$ point played is
$$p^k \binom{k-1+i}{i}(1-p)^i. $$
Hence,
\[P(k,p)=p^k \sum_{i=0}^{k-1}\binom{k-1+i}{i}(1-p)^i=p^k\sum_{j=0}^{k-1}(-1)^j\left(\sum_{i=j}^{k-1}\binom{i}{j}\binom{k-1+i}{i}\right) p^j.\]

We have

\begin{align*}
\sum_{i=j}^{k-1}\binom{i}{j}\binom{k-1+i}{i}&=\sum_{i=j}^{k-1}\binom{k-1+i}{i-j}\binom{k-1+j}{j}=\binom{k-1+j}{j}\binom{2k-1}{k+j}\\
&\phantom{=}\\
&=\frac{k}{k+j}\binom{k+j}{j}\binom{2k-1}{k+j}=\frac{1}{2}\binom{2k}{k}\binom{k-1}{j}\frac{k}{k+j}.
\end{align*}

\vspace{.1in}

Hence, 
\[P(k,p)=\frac{1}{2}k\binom{2k}{k}\sum_{j=0}^{k-1}(-1)^j\binom{k-1}{j}\frac{1}{k+j}p^{k+j}.\]

Taking the derivative with respect to $p$, we have

\[P'(k,p)=\frac{1}{2}k\binom{2k}{k}\sum_{j=0}^{k-1}(-1)^j\binom{k-1}{j}p^{k+j-1}=\frac{1}{2}k\binom{2k}{k}(pq)^{k-1}.\]




\end{proof}




\begin{lem}

The function \[r_{n,k}(p)=\frac{P'(n,k,p)}{P'(nk,p)}\] is a 
decreasing function of $p$,\ for $.5\le p<1$.

\end{lem}

\begin{proof}
\begin{align*}
r_{n,k}(p)&=\frac{P'(n,k,p)}{P'(nk,p)}=\frac{P'(n,P(k,p))}{P'(nk,p)}\\
&\phantom{=}\\
&=\frac{\frac{1}{2}n\binom{2n}{n}\left(P(k,p)Q(k,p)\right)^{n-1}\frac{1}{2}k\binom{2k}{k}(pq)^{k-1}}{\frac{1}{2}nk\binom{2nk}{nk}(pq)^{nk-1}}\\
&\phantom{=}\\
&=\frac{1}{2}\frac{\binom{2n}{n}\binom{2k}{k}\left(P(k,p)Q(k,p)\right)^{n-1}}{\binom{2nk}{nk}(pq)^{k(n-1)}},\hspace{.7 in} \ .5\le p<1.\hspace{.5 in}(6)
\end{align*}


Substituting from Lemma 2, we have

\[r_{n,k}(p)=\frac{1}{2}\frac{\binom{2n}{n}\binom{2k}{k}}{\binom{2nk}{nk}}\left(\sum_{i=0}^{k-1}a_{k,i}(pq)^i\right)
^{n-1},\]
where $\displaystyle  a_{k,i}=\frac{1}{2}\binom{2k}{k}\binom{2i}{i}\frac{k}{k+i}.$
\vspace{.2in}

Since $a_{k,i}>0$, and $pq$ is a 
decreasing function of $p$, it follows that $r_{n,k}(p)$ is a  decreasing function of $p$.

\end{proof}

\begin{lem}
If $2 \leq t \leq m$, then
\[4^t\frac{\binom{2m-2t}{m-t}}{\binom{2m}{m}}\frac{2m-t}{m}>2\ .\]
\end{lem}

\begin{proof}

For $t=2$, the left hand side of Lemma 5 reduces to
\[\frac{8(m-1)^2}{(2m-1)(2m-3)}=2+\frac{2}{(2m-1)(2m-3)}\]
which is clearly greater than $2$ when $m\ge 2$. We show by induction that Lemma 5 holds for all $t$. Suppose it is true for some $t$, and consider the left hand 
side of Lemma 5 with $t$ replaced by $t+1$. We have, 

\begin{align*}
4^{t+1}\frac{\binom{2m-2t-2}{m-t-1}}{\binom{2m}{m}}\frac{2m-t-1}{m}&=4\left(4^t\frac{\binom{2m-2t}{m-t}}{\binom{2m}{m}}\frac{2m-t}{m}\right)\frac{(m-t)^2}{(2m-2t-1)(2m-2t)}\frac{2m-t-1}{2m-t}\\
&\phantom{=}\\
&>\frac{4(m-t)(2m-t-1)}{(2m-2t-1)(2m-t)}. 
\end{align*}

The right hand side of the inequality is greater than $2$ when $m>t$ since
\[\frac{4(m-t)(2m-t-1)}{(2m-2t-1)(2m-t)} =2+\frac{2t}{(2m-2t-1)(2m-t)}.\]

When $m=t$, and $t\ge 2$, it is  shown easily by induction that $\displaystyle\frac{4^t}{\binom{2t}{t}}>2$.

\end{proof}

\begin{lem}
If $n\ge 2$  and $k\ge 2$, then
$r_{n,k}(.5)>1$.

\end{lem}

\begin{proof}

Noting that $P(k,.5)=Q(k,.5)=.5$, we have from (6),

\[r_{n,k}(.5)=\frac{1}{2}\frac{\binom{2n}{n}\binom{2k}{k}}{\binom{2nk}{nk}}4^{(k-1)(n-1)}.\]

Lemma 6 is true for $k=2$, since we have

\[r_{n,2}(.5)=3\  4^{n-1}\frac{\binom{2n}{n}}{\binom{4n}{2n}}>1,\]

\noindent and we apply Lemma 5 with $m=2n$ and $t=n$. 

We show by induction that Lemma 6 holds for all $k$. Suppose it is true for some $k$, and consider Lemma 6 with $k$ replaced by $k+1$.

\begin{align*}
r_{n,k+1}(.5)&=\frac{1}{2}\frac{\binom{2n}{n}\binom{2k+2}{k+1}}{\binom{2nk+2n}{nk+n}}4^{k(n-1)}\\
&\phantom{=}\\
&=4^{n-1}\left(\frac{1}{2}\frac{\binom{2n}{n}\binom{2k}{k}}{\binom{2nk}{nk}}4^{(k-1)(n-1)}\right)\frac{(2k+2)(2k+1)}{(k+1)^2}\frac{\binom{2nk}{nk}}{\binom{2nk+2n}{nk+n}}\\
&\phantom{=}\\
&>\frac{1}{2}4^n\frac{\binom{2nk}{nk}}{\binom{2nk+2n}{nk+n}}\frac{2k+1}{k+1}>1.
\end{align*}

\noindent The final inequality is obtained by applying Lemma 5 with $m=nk+n$ and $t=n$.

\end{proof}

\setcounter{theo}{0}

\begin{theo}
If $n\ge 2,\ k\ge 2,$ and $ .5<p<1$, then
$P(n,k,p)>P(nk,p)$.
\end{theo}

\begin{proof}
We have $P(n,k,.5)=P(nk,.5)=.5$, and $P(n,k,1)=P(nk,1)=1$.
\vspace{.2 in}


If there existed a point $p_1$, $.5<p_1<1$, such that $P(n,k,p_1)=P(nk,p_1)$, then $\displaystyle r_{n,k}(p)=\frac{P'(n,k,p)}{P'(nk,p)}$ would need to be $1$ at least twice, once on the interval $.5<p<p_1$ and once on the interval $p_1<p<1$ (since $r_{n,k}(p)$ cannot be greater than $1$ (or less than $1$) over the full extent of either interval). But $r_{n,k}(p)$ cannot be $1$ at least twice because we know from Lemma 4 that $r_{n,k}(p)$ is a  decreasing function of $p$. Hence, either $P(n,k,p)>P(nk,p)$, or \mbox{$P(nk,p)>P(n,k,p)$}, on the interval $.5<p<1$.  Since we know from Lemma 6 that $r_{n,k}(.5)>1$, we must have $P(n,k,p)>P(nk,p)$ over that same range. 

\end{proof}

\begin{lem}

Let \[f(n,x)=\sum_{i=0}^{n-1}a_{n,i}x^i.\] If the function

\[h(n,k,x)=(n-1)f(n,x)f'(k,x)-(k-1)f(k,x)f'(n,x)\]

\noindent has at most one positive zero, then the functions $P(n,k,p)$ and $P(k,n,p)$ cannot intersect on the interval $.5<p<1$.

\begin{proof}
Let \[R_{n,k}(p)=\frac{P'(n,k,p)}{P'(k,n,p)}.\]
Looking at the proof of Lemma 4 we see that
 \[R_{n,k}(p)=\frac{\frac{1}{2}n\binom{2n}{n}\left(P(k,p)Q(k,p)\right)^{n-1}\frac{1}{2}k\binom{2k}{k}(pq)^{k-1}}{\frac{1}{2}k\binom{2k}{k}\left(P(n,p)Q(n,p)\right)^{k-1}\frac{1}{2}n\binom{2n}{n}(pq)^{n-1}}.\]

Substituting from Lemma 2, and simplifying, we have 

\[R_{n,k}(p)=\frac{f(k,pq)^{n-1}}{f(n,pq)^{k-1}},\hspace{.5 in}.5\le p<1.\]

Following the simple argument made in the  the proof of Theorem 1, if  $P(n,k,p)$ and $P(k,n,p)$ intersected on $.5<p<1$, $R_{n,k}(p)$ would equal $1$ at least twice on that interval. Furthermore, since $f(n,.25)=4^{n-1}$ and \mbox{$f(k,.25)=4^{k-1}$} (see Lemma 2 with $p=.5$ and $pq=.25$), $R_{n,k}(.25)=1$. Hence, there would be at least three different values of $pq$ for which $R_{n,k}(p)=1$. 

Therefore, the logarithm of $R_{n,k}(p)$ would equal $0$ at least three times, and the derivative of that logarithm with respect to $pq$ would equal $0$ at least twice. The derivative of the logarithm of $R_{n,k}(p)$ with respect to $pq$ is equal to

\[\frac{h(n,k,pq)}{f(n,pq)f(k,pq)},\] proving the Lemma.

\end{proof}

\end{lem}

\begin{lem}

Let $\{a_i\}_1^n$ be a sequence such that $a_1<0$, $\displaystyle \sum_{i=1}^n a_i\le 0$ and such that either
\vspace{.15 in}

\noindent Case 1: $a_i\le 0$ \ if \ $2\le i\le n$, or \newline 
Case 2: there exists a $t\le n$ such that $a_i\le 0$ \ if \ $2\le i<t$, and $a_i>0$\  if \ $i\ge t$. 
\vspace{.03 in}

\noindent holds.

\vspace{.2 in}
Let $\{r_i\}_1^n$ be a sequence such that for all $i$, $r_i>0$ and $r_{i+1}<r_i$.
\vspace{.2 in}

Then $\displaystyle \sum_{i=1}^n r_ia_i<0$.

\begin{proof}

The Lemma is obvious for Case 1.  

\vspace{.2 in}

For Case 2,  $\displaystyle \sum_{i=1}^n r_ia_i-\sum_{i=1}^n r_t a_i<0$, since $(r_1-r_t)a_1$\ is negative, and if $i>1$, $r_i-r_t$  is positive  when $a_i$ is negative or zero, and zero or negative when $a_i$ is positive. Hence,

\[\sum_{i=1}^n r_ia_i<\sum_{i=1}^n r_ta_i\le 0.\]

\end{proof}
\end{lem}



\begin{lem}

Each of the ratios $\displaystyle \frac{a_{n,t}}{a_{n,t-1}}$ and $\displaystyle \frac{a_{n+1,t}}{a_{n,t-1}}$ decreases as\ $t$ 
decreases.

\end{lem}

\begin{proof}

\[\frac{a_{n,t}}{a_{n,t-1}}-\frac{a_{n,t-1}}{a_{n,t-2}}=\frac{2\left(1+n^2+2n(t-1)
+t(3t-5)\right)}{t(t-1)(n+t-1)(n+t)},\]
which is  positive for $t\ge 2$ and $n\ge 3$.

\[\frac{a_{n+1,t}}{a_{n,t-1}}-\frac{a_{n+1,t-1}}{a_{n,t-2}}=\frac{4(2n+1)\left(n(n-1)+2nt+t(5t-7)\right)}{(t-1)tn(n+t)(n+1+t)},\]
which is  positive for $t\ge 2$ and $n\ge 3$.


\end{proof}

We note that,  
as defined, the quantity $R_{n,k}(1)$ is indeterminate. 
We take $R_{n,k}(1)$ to mean 
$\displaystyle \lim_{p\rightarrow 1}R_{n,k}(p)$.

\begin{lem}
If $1 < k < n$ then $R_{n,k}(1)<1$.
\end{lem}

\begin{proof}



\vspace{.2 in}

Noting  that $pq=0$ when $p=1$,
\[R_{n,k}(1)=\frac{f(k,0)^{n-1}}{f(n,0)^{k-1}}=\frac{a_{k,0}^{n-1}}{a_{n,0}^{k-1}}=\frac{\left (\frac{1}{2}\binom{2k}{k}\right )^{n-1}}{\left (\frac{1}{2}\binom{2n}{n}\right )^{k-1}},\]



$\displaystyle \mbox{Let}\ u_{n,k}=\frac{R_{n+1,k}(1)}{R_{n,k}(1)}=\left ( \frac{n+1}{4n+2}\right )^{k-1}\frac{1}{2}\binom{2k}{k},\  \mbox{and}$


\vspace{.2in}

$\displaystyle \mbox{Let}\  v_{n,k}=\frac{u_{n,k+1}}{u_{n,k}}=\frac{n+1}{4n+2}\left/\frac{k+1}{4k+2}\right . $

\vspace{.1in}

It is assumed in the following that $1 < k < n$.
\vspace{.1in}

$v_{n,k}<1$, since $n>k$, and the function $\frac{r+1}{4r+2}$ is a decreasing function of $r$ ;
\vspace{.05in}

Since $v_{n,k}<1$, $u_{n,k}$ is a decreasing function of $k$, and since $u_{n,1}=1$, $u_{n,k}<1$;
\vspace{.05in}

Since $u_{n,k}<1$ , $R_{n,k}(1)$ is a decreasing function of $n$, and since $R_{k,k}(1)=1$, $R_{n,k}(1)<1$.



\end{proof}

\begin{theo}
If $2 \leq k \leq n$ and $.5<p<1$, then
$P(n,k,p)>P(k,n,p)$.
\end{theo}

\begin{proof}

The $h(n,k,x)$ of Lemma 7 can be written as

\[h(n,k,x)=(n-1)\sum_{i=0}^{n-1}a_{n,i}x^i \sum_{i=0}^{k-1}ia_{k,i}x^{i-1}-(k-1)\sum_{i=0}^{k-1}a_{k,i}x^i \sum_{i=0}^{n-1}ia_{n,i}x^{i-1}=\sum_{r=0}^{n+k-3}c_{n,k,r}x^r.\]

We show that $h(n,k,x)$ has at most one positive zero by showing that the sequence $\displaystyle \{c_{n,k,r}\}_{r=0}^{n+k-3}$ has exactly one change in sign, and applying Descartes' Rule of Signs. 


We do this by considering four cases,
\vspace{.2 in}

\noindent Case 1: $0\le r\le k-2$. We show that $c_{n,k,r}>0$.

\noindent Case 2: $k-1\le r\le n-2$. We show that if $c_{n,k,r}\le 0$, then $c_{n,k,r+1}< 0$.

\noindent Case 3: $n-1\le r \le n+k-4$. We show that $c_{n,k,r}<0$.

\noindent Case 4: $r=n+k-3$. We show that $c_{n,k,r}=0$.

\vspace{.2 in}
\noindent \bf Case 1: $0\le r\le k-2.$\rm

\[c_{n,k,r}=\sum_{j=0}^{r+1}\left((n-1)j-(k-1)(r+1-j)\right)a_{k,j}a_{n,r+1-j}. \]
 
We see that $c_{n,k,r}$ is an increasing function of $n$, since the bracketed term in $c_{n,k,r}$ is an increasing funtion of $n$, and

\[\frac{a_{n+1,t}}{a_{n,t}}=1+\frac{3n^2+n+2t+3nt}{n(n+t+1)}>1.\] 

Since $c_{k,k,r}=0$, $c_{n,k,r}>0$.
\vspace{.2 in}


\noindent \bf Case 2: $k-1\le r\le n-2.$\rm

\[c_{n,k,r}=\sum_{j=0}^{k-1}\left((n-1)j-(k-1)(r+1-j)\right)a_{k,j}a_{n,r+1-j}\]

Let \[b(n,k,r,j)=\left((n-1)j-(k-1)(r+2-j)\right)a_{k,j}a_{n,r+1-j},\]

so that

\[c_{n,k,r+1}=\sum_{j=0}^{k-1}b(n,k,r,j)\frac{a_{n,r+2-j}}{a_{n,r+1-j}}.\]

We see that $b(n,k,r,0)<0$, the bracketed term in $b(n,k,r,j)$ increases as $j$ increases, and if $c_{n,k,r}\le 0$, then  $\displaystyle \sum_{j=0}^{k-1}b(n,k,r,j)<0$(since the bracketed term in $b(n,k,r,j)$ is less than  the bracketed term in $c_{n,k,r}$). Furthermore, we know from Lemma 9  that the sequence $\displaystyle \left\{\frac{a_{n,r+2-j}}{a_{n,r+1-j}}\right\}$ is decreasing as $j$ increases.
\vspace{.1 in}
 
Hence the conditions set forth in Lemma 8 are met, and we have \mbox{$c_{n,k,r+1}<0.$}

\vspace{.2 in}

\noindent \bf Case 3: $n-1\le r\le n+k-4$. \rm

\vspace{.2 in}
Let $r=n-1+t$, \ $0\le t\le k-3$.

\[c_{n,k,n-1+t}=\sum_{j=t+1}^{k-1}\left((n-1)j-(k-1)(n+t-j)\right)a_{k,j}a_{n,n+t-j}.\]

Let $b(n,k,t,j)=\left(nj-(k-1)(n+1+t-j)\right)a_{k,j}a_{n,n+t-j}$, so that

\[c_{n+1,k,n+t}=\sum_{j=t+1}^{k-1}b(n,k,t,j)\frac{a_{n+1,n+1+t-j}}{a_{n,n+t-j}}.\]

We see that $b(n,k,t,t+1)=\left(n(t-(k-2))\right)a_{k,j}a_{n,n-1} < 0$,
the bracketed term in $b(n,k,t,j)$ increases as $j$ increases, and if
$c_{n,k,n-1+t}<0$, then  \mbox{$\displaystyle
\sum_{j=t+1}^{k-1}b(n,k,t,j)<0$} (since the bracketed term in
$b(n,k,t,j)$ is less than or equal to the bracketed term in
$c_{n,k,n-1+t}$). Furthermore, from Lemma 9 we know that the sequence
$\displaystyle \left \{\frac{a_{n+1,n+1+t-j}}{a_{n,n+t-j}}\right \}$ is
decreasing as $j$ increases.

\vspace{.1 in}

Hence the conditions set forth in Lemma 8 are met, and we have \mbox{$c_{n+1,k,n+t}<0$}. Since $c_{k,k,k-1+t}=0$, we have for all $n>k$, $c_{n,k,n-1+t}<0.$

\vspace{.2 in}

\noindent \bf Case 4: $r=n+k-3$. 

$c_{n,k,r}=\left((n-1)(k-1)-(k-1)(n-1)\right)a_{n,n-1}a_{k,k-1}=0$.

\vspace{.4 in}
\rm We have proved that $h(n,k,x)$ has at most one positive zero. Hence we know from Lemma 7 that on the interval $.5<p<1$, $P(n,k,p$) and $P(k,n,p)$ 

\vspace{.1 in}

\noindent cannot intersect. From Lemma 10, we know that  
$\displaystyle \lim_{p\rightarrow 1}\frac{P'(n,k,p)}{P'(k,n,p)}<1$. Hence, we must have $P(n,k,p)>P(k,n,p)$ on $.5<p<1$.


\end{proof}

\section{Counterexamples for two conjectured inequalities}

\vspace{.3in}

Define ${\rm Maxpoints} (m,n) :=(2m-1)(2n-1)$,
the maximum number of  points possible where the winner is the first player
to win $m$ $n$-point games.

Initial examination of numerical values of $P(n,k,p)$ for a wide range
of values of $n$, $k$ and $p$  suggested that the following conjectured
inequalities might be universally true and provable ($.5<p<1$):

\begin{conjecture}
If ${\rm Maxpoints}(a,b)>{\rm Maxpoints}(c,d)$, then
$P(a,b,p)>P(c,d,p)$.
\end{conjecture}

\begin{conjecture}
If $ab=cd$  and  $\min(a,b)>\min(c,d)$, then
$P(a,b)>P(c,d)$.
\end{conjecture}

\rm The following computations
show that neither of these conjectures is universally true:
\vspace{.3in}

\(\begin{array}{lr}
{\rm Maxpoints}(3,2)=15&P(3,2,.6)=.7617 \cdots\\
{\rm Maxpoints}(1,7)=13&P(7,.6)=.7711 \cdots
\end{array}\)

\vspace{.3in}

\(\begin{array}{ll}
\min{(4,3)}=3&P(4,3,.99)=.999999999999999999670 \cdots\\
\min{(6,2)}=2&P(6,2,.99)=.999999999999999999676 \cdots
\end{array}\)

\section{Remark}

The integers $\displaystyle a_{k,i}$, which play a significant role in
this paper, are the same as the integers $\displaystyle a_{k+i-1,k-1}$
in  A033820 of the On-line Encyclopedia of Integer Sequences. They
appear in quite different contexts in \cite{ref1,ref2}.

\begin{thebibliography}{9}

\bibitem{ref1} A. Burstein, Enumeration of words with forbidden patterns,
Ph.\ D. Thesis, U. of Pennsylvania, 1998.

\bibitem{ref2} I. Gessel, Super ballot numbers,
{\it J. Symbolic Computation} {\bf  14} (1992), 179--194.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 60C05.

\noindent \emph{Keywords:} games, inequalities, probability, sets.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A033820}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 29 2003; 
revised version received   November 24 2003.
Published in {\it Journal of Integer Sequences}, December 6 2003.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in


\end{document}

                                                                                



\end{document}