Prove that from $x + y = 1 \ (x, y \in \mathbb R)$ it follows that \[x^{m+1} \sum_{j=0}^n \binom{m+j}{j} y^j + y^{n+1} \sum_{i=0}^m \binom{n+i}{i} x^i = 1 \qquad (m, n = 0, 1, 2, \ldots ).\]
Problem
Source:
Tags: algebra, Summation, binomial coefficients, Binomial coefficient identity, combinatorics, IMO Shortlist
iarnab_kundu
16.10.2013 00:53
I am going to use the result that \[\binom{n}{k}=(-1)^k\binom{k-n}{k}\] Now \[ x^{m+1}\sum_{j=0}^n\binom{m+j}{j}y^j+y^{n+1}\sum_{i=0}^m\binom{n+i}{i}x^i \]\[=\[ x^{m+1}\sum_{j=0}^n(-1)^j\binom{-m}{j}y^j+y^{n+1}\sum_{i=0}^m(-1)^i\binom{-n}{i}x^i \]\[=x^{m+1}(1-y)^{-m}+y^{n+1}(1-x)^{-n}=x+y=1\]
Tintarn
18.03.2016 00:10
iarnab_kundu wrote: I am going to use the result that \[\binom{n}{k}=(-1)^k\binom{k-n}{k}\]Now \[ x^{m+1}\sum_{j=0}^n\binom{m+j}{j}y^j+y^{n+1}\sum_{i=0}^m\binom{n+i}{i}x^i \]\[= x^{m+1}\sum_{j=0}^n(-1)^j\binom{-m}{j}y^j+y^{n+1}\sum_{i=0}^m(-1)^i\binom{-n}{i}x^i \]\[=x^{m+1}(1-y)^{-m}+y^{n+1}(1-x)^{-n}=x+y=1\] So you claim that \[\sum_{j=0}^n (-1)^j \binom{-m}{j} y^j=(1-y)^{-m}?\]This clearly seems to be wrong.. Here is my solution which is just a small adaption of this proof for the special case $x=y=\frac{1}{2}$.
We have $m+n+1$ balls in a row and we are colouring them randomly with two colours, black and red, such that any ball is coloured red with probability $x$ and black with probability $y$.
Let $A$ be the probability that at least $n+1$ balls are black and let $B$ be the probability that at least $m+1$ balls are red. Clearly $A+B=1$.
Now, for any possibility in $A$, we look at the $(n+1)$-th ball from the left which is coloured black. Let it be on the $(n+i+1)$-th position from the left with $0 \le i \le n$. Then for any such position, we have exactly $\binom{n+i}{i}$ ways to choose the $n$ black balls left from it and the probability for every such constellation is $x^iy^{n+1}$. Now, doing this for $k=0,1,\dotsc,m$, we obtain $A=y^{n+1}\sum_{i=0}^m \binom{n+i}{i} x^i$.
Similarly, we obtain $B=x^{m+1}\sum_{j=0}^n \binom{m+j}{j} y^j$. Done!
darij grinberg
22.03.2018 05:54
An algebraic proof now appears in the solution to Exercise 2.25 of Darij Grinberg, Notes on the combinatorial fundamentals of algebra, 21 March 2018. (It's a fairly boring sum-manipulation argument, relying on a variant of Vandermonde convolution.) The exercise has also been mentioned in https://artofproblemsolving.com/community/c6h1320666_binomial_coefficient_problem .
adhikariprajitraj
22.03.2018 06:04
darij grinberg wrote: An algebraic proof now appears in the solution to Exercise 2.25 of Darij Grinberg, Notes on the combinatorial fundamentals of algebra, 21 March 2018. (It's a fairly boring sum-manipulation argument, relying on a variant of Vandermonde convolution.) Hello sir where can I find your pdfs?
Amir Hossein
23.03.2018 00:49
darij grinberg wrote: ... Darij Grinberg, Notes on the combinatorial fundamentals of algebra, 21 March 2018... Woah, that's a 1008 page PDF file! How long did it take you to write it? Thanks for sharing, Darij!
darij grinberg
23.03.2018 02:56
adhikariprajitraj wrote: Hello sir where can I find your pdfs? Click on the "sols.pdf" link in the release. There is also a version on my website that gets updated, but those updates tend to mess with the numbering of the exercises, so I prefer linking to a frozen version when I cite stuff. Amir Hossein wrote: darij grinberg wrote: ... Darij Grinberg, Notes on the combinatorial fundamentals of algebra, 21 March 2018... Woah, that's a 1008 page PDF file! How long did it take you to write it? Thanks for sharing, Darij! Half of it is bookkeeping indices in summations I've started in 2015, when I was giving homework to some students I mentored. I still tend to update the document with materials I've written for my classes, once those classes are over. For example, the exercise above has gotten in because I gave it as a homework exercise in Math 4707 at UMN and so had a solution prepared anyway.
Amir Hossein
27.03.2018 05:13
darij grinberg wrote: I've started in 2015, when I was giving homework to some students I mentored. I still tend to update the document with materials I've written for my classes, once those classes are over. For example, the exercise above has gotten in because I gave it as a homework exercise in Math 4707 at UMN and so had a solution prepared anyway. That's just awesome. Keep up the good work and keep us posted!
WolfusA
17.06.2018 12:32
Crux v24 n8 Mathematical Mayhem: 1998-1999 Olympiad Correspondence Problems Task 12
chaotic_iak
19.06.2018 11:16
I don't see a combinatorial proof, so here it is. Suppose Xerneas and Yveltal are competing in a match. The match lasts for a number of games; in each game, Xerneas wins with fixed probability $x$ and Yveltal wins with fixed probability $y$, and there are no ties. (Thus $x + y = 1$.) Moreover, the match ends either when Xerneas has scored $m+1$ wins, or Yveltal has scored $n+1$ wins. Let's consider the probability that the match ends. On one hand, the match must end, since after each game one player will score a win, thus after $m+n+1$ games either Xerneas has scored $m+1$ wins or Yveltal has scored $n+1$ wins. Thus the probability that the match ends is 1, the RHS. On the other hand, consider a sequence of winners of the match. There are two cases: Xerneas wins the match, or Yveltal wins the match. I will discuss the first case; the second case is symmetric. If Xerneas wins the match, then Xerneas must have won exactly $m+1$ games; moreover, the last game must have been won by Xerneas (otherwise the match continued even after Xerneas has scored $m+1$ wins, impossible). Suppose Yveltal has won $j$ games. Clearly $0 \le j \le n$; if $j \ge n+1$ then Yveltal would have won beforehand. The probability that this particular sequence occurs is thus $x^{m+1} y^j$: Xerneas wins $m+1$ games and Yveltal wins $j$ games, in the exact order as the sequence gives. For any fixed $j$, there are $\binom{m+j}{j}$ possible sequences: the last game must be won by Xerneas, but in the first $m+j$ games, there are $j$ that Yveltal wins and they can be permuted arbitrarily. Thus for a fixed $j$, the probability that Xerneas wins with a score of $m+1$ vs $j$ is $\binom{m+j}{j} x^{m+1} y^j$. The probability that Xerneas wins the match is thus simply the sum over all $j = 0, 1, 2, \ldots, n$, namely the first term of the LHS. The same argument can be applied, and the probability that Yveltal wins the match is the second term of the LHS. The probability that the match ends is simply the sum of these two probabilities, since there is no other possible outcome (no ties etc). Thus the probability that the match ends is the LHS. This proves the claim.
Tintarn
19.06.2018 13:56
chaotic_iak wrote: I don't see a combinatorial proof, so here it is. Huh? How is my proof in #4 not a combinatorial one? Which btw is the only proof of the claim in this thread before your post. And which btw is identical with yours.
chaotic_iak
19.06.2018 23:25
Tintarn wrote: Huh? How is my proof in #4 not a combinatorial one? Good point. I completely missed the hide tag, oops.
onyqz
14.11.2024 22:45
that was exhausting to write up...
We first note that it holds for $m,n=0$.
Suppose that it holds for $m,n$. We now induct on $n$ and show that it also holds for $m,n+1$. This can then be done in the same way for induction on $m$.
Then for $m,n+1$, the LHS turns out to be
\begin{align*}
x^{m+1} \sum_{j=0}^{n+1} \binom{m+j}{j} y^j + y^{n+2} \sum_{i=0}^m \binom{n+1+i}{i} x^i &= x^{m+1} \sum_{j=0}^{n} \binom{m+j}{j} y^j + {m+n+1 \choose n+1}x^{m+1}y^{n+1} + y^{n+2} \sum_{i=0}^m \binom{n+1+i}{i} x^i \\
&= x^{m+1} \sum_{j=0}^{n} \binom{m+j}{j} y^j + {m+n+1 \choose n+1}x^{m+1}y^{n+1} + y^{n+1} \sum_{i=0}^m y\cdot\frac{n+1+i}{n+1}\binom{n+i}{i} x^i \\
&= \left(1-y^{n+1}\sum_{i=0}^m{n+i\choose i}x^i\right) + {m+n+1 \choose n+1}x^{m+1}y^{n+1} + y^{n+1} \sum_{i=0}^m y\cdot\frac{n+1+i}{n+1}\binom{n+i}{i} x^i \\
\end{align*}So we want to prove
$$y^{n+1}\left({m+n+1 \choose n+1}x^{m+1}-\sum_{i=0}^m{n+i\choose i}x^i + \frac{y}{n+1}\cdot\sum_{i=0}^m (n+1+i)\binom{n+i}{i} x^i\right)=0 \, ,$$that is
\begin{align*}
{m+n+1 \choose n+1}x^{m+1}-\sum_{i=0}^m{n+i\choose i}x^i + \frac{y}{n+1}\cdot\sum_{i=0}^m (n+1+i)\binom{n+i}{i} x^i = 0 \Longleftrightarrow \\
\end{align*}\begin{align*}
\sum_{i=0}^m{n+i\choose i}x^i&={m+n+1 \choose n+1}x^{m+1} + \frac{y}{n+1}\cdot\sum_{i=0}^m (n+1+i)\binom{n+i}{i} x^i \Longleftrightarrow\\
(n+1)\sum_{i=0}^m{n+i\choose i}x^i&=(m+n+1){m+n\choose n}x^{m+1}+y\sum_{i=0}^m (n+1+i)\binom{n+i}{i} x^i \Longleftrightarrow\\
(1-x) \sum_{i=0}^m (n+1+i)\binom{n+i}{i} x^i &= (n+1)\sum_{i=0}^m{n+i\choose i}x^i -(m+n+1){m+n\choose n}x^{m+1} \Longleftrightarrow \\
\sum_{i=0}^m (n+1+i)\binom{n+i}{i} x^i &= (n+1)\sum_{i=0}^m{n+i\choose i}x^i+\sum_{i=0}^{m-1}(n+1+i){n+i\choose i}x^{i+1} \Longleftrightarrow \\
\sum_{i=0}^m (n+1+i)\binom{n+i}{i} x^i &= (n+1)\sum_{i=0}^m{n+i\choose i}x^i+\sum_{i=1}^{m}(n+i){n+i-1\choose i-1}x^{i}
\end{align*}Finally we have to prove
\begin{align*}
\sum_{i=0}^m \left((n+1+i)\binom{n+i}{i}-(n+i){n+i-1\choose i-1}\right)x^i
&=\sum_{i=0}^m \left((n+1+i)\binom{n+i}{i}-i{n+i\choose i}\right)x^i\\
&=\sum_{i=0}^m (n+1){n+i\choose i}x^i \, ,\\
\end{align*}which is seen to be true.
This concludes the problem. $\square$