Posted Feb. 8, 2008
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+( 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