IMO 1975 SL 7

Origin: GDR

Problem

Prove that from x + y = 1 (x, y \inR) it follows that xm+1 n  j=0 m + j j  yj + yn+1 m  i=0 n + i i  xi = 1 (m, n = 0, 1, 2, . . .).

Solution

We use induction on m. Denote by Sm the left-hand side of the equality to be proved. First S0 = (1−y)(1 +y+\cdot \cdot \cdot+yn)+yn+1 = 1, since x = 1−y. Furthermore, Sm+1 −Sm

m + n + 1 m + 1  xm+1yn+1 + xm+1 n  j=0 m + 1 + j j  xyj − m + j j  yj 

m + n + 1 m + 1  xm+1yn+1 +xm+1 n  j=0 m + 1 + j j  yj − m + j j  yj − m + 1 + j j  yj+1  = xm+1 ⎡ ⎣ m + n + 1 n  yn+1 + n  j=0 m + j j −1  yj − m + j + 1 j  yj+1 ⎤ ⎦ = 0; i.e., Sm+1 = Sm = 1 for every m. Second solution. Let us be given an unfair coin that, when tossed, shows heads with probability x and tails with probability y. Note that xm+1
m+j j  yj is the probability that until the moment when the (m+1)th head appears, exactly j tails (j < n + 1) have appeared. Similarly, yn+1
n+i i  xi is the probability that exactly i heads will appear before the (n + 1)th tail occurs. Therefore, the above sum is the probability that either m + 1 heads will appear before n + 1 tails, or vice versa, and this probability is clearly 1.