#
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) 3^{n-2k}

**Solution 1**. By *Shalosh B. Ekhad* .
Go to Maple, and type:
with(SumTools[Hypergeometric]);
evalb(degree(normal(Zeilberger(binomial(n,k)*binomial(2*k,k),n,k,N)[1]/
Zeilberger(binomial(n,2*k)*binomial(2*k,k)*3^(n-2*k),n,k,N)[1]),N)=0);

**Solution 2.** By
*Omar Khayyam*. Take the constant term in :
( 1+ (x+x^{-1})^{2})^{n}=
(3+( x^{2}+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
3^{n-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)
p^{k}(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