Four Solutions to David Beckwith's American Mathematical Monthly Problem 11343 (Feb. 2008)

Compiled by Doron Zeilberger

Posted Feb. 8, 2008

11343. Proposed by David Beckwith, Sag Harbor, NY. Show that when n is a positive integer,
Σ k ≥ 0 binomial(n,k) binomial(2k,k) = Σ k ≥ 0 binomial(n,2k) binomial(2k,k) 3n-2k
Solution 1. By Shalosh B. Ekhad . Go to Maple, and type:
Solution 2. By Omar Khayyam. Take the constant term in : ( 1+ (x+x-1)2)n= (3+( x2+x-2 ) )n   .

Solution 3. By Blaise Pascal. You live n days. At each day, you toss a coin. If it is Head, you do nothing. If it is Tail, you get to toss another coin twice, once in the Morning, and once in the Evening. If this other coin is Head you win 50 cents, otherwise you lose 50 cents. In how many ways can this be done if you die breaking even?

This can be counted in TWO ways.

First Way: You got to play in k days, (k=0..n). First choose the k days where you got to play, and then look at the 2k coin tosses, in those playing days, that result with breaking even.

Second Way: There are 5 kinds of days.

(i) you didn't play
(ii) you played and won in the morning and lost in the evening
(iii) you played and lost in the morning and won in the evening
(iv) you won a dollar
(v) you lost a dollar

If there are n-2k days where you neither won nor lost (2k ≤ n), and 2k days where you either won a dollar or lost a dollar, then there binomial(n,2k) ways of choosing those. Having chosen them, there are 3n-2k ways of deciding, for the break-even days, which of the three types these are. As for the other 2k days, where you won or lost, there are binomial(2k,k) ways of deciding how the k good days and k bad days are distributed.

Solution 4. By Leonhard Euler . Convert both sides to hypergeometric notation, and use one of my transformations.

Remark: All the above proofs can be easily modified to prove the more general

Σ k ≥ 0 binomial(n,k) binomial(2k,k) pk(1-p)(n-k) = Σ k ≥ 0 binomial(n,2k) binomial(2k,k) (2-p)(n-2k) (1-p)2k

Personal Journal of S.B. Ekhad and D. Zeilberger