Let x be a real number and put y = (x + 1)/2. Put an = 1 + x + x2 + ... + xn, and bn = 1 + y + y2 + ... + yn. Show that ∑0n am (n+1)C(m+1) = 2n bn, where aCb is the binomial coefficient a!/( b! (a-b)! ).
Solution
The coefficient of xk on the lhs is n+1Ck+1 + n+1Ck+2 + n+1Ck+3 + ... + n+1Cn+1.The coefficient on the rhs is 2n-kkCk + 2n-k-1k+1Ck + 2n-k-2k+2Ck + ... + nCk. If n-k=0 these are both 1. We use induction on n-k. Suppose the result is true for 0, 1, ... , n-k-1. We have n+1Ck+1 + n+1Ck+2 + n+1Ck+3 + ... + n+1Cn+1 = (nCk + nCk+1) + (nCk+1 + nCk+2) + ... + (nCn-1 + nCn) + n+1Cn+1 = nCk + 2(nCk+1 + nCk+2 + ... + nCn) = nCk + 2(2n-k-1kCk + 2n-k-2k+1Ck + 2n-k-3k+2Ck + ... + n-1Ck) = 2n-kkCk + 2n-k-1k+1Ck + 2n-k-2k+2Ck + ... + 2 n-1Ck + nCk, which is the required result for n-k.
© John Scholes
jscholes@kalva.demon.co.uk
1 Nov 2003
Last corrected/updated 1 Nov 03