Question

How can this be proven?

Answer 1

The right-hand side is the number of binary strings of length 2n, consisting of 0s and 1s.

For k < n, the term of index k on the left is the number of such strings in which the digit in position n + k + 1 occurs there for the (n + 1)st time. When k = n, it is the number of strings in which there are n 0s and n 1s.

This proves the equality.

Answer 2

The problem with using induction is that since the highest value of k reaches n (or n+1 in the induction step), can we really substitute, in the case of n+1, the left side as 2\^2n and then write the equation for n+1 as 2\^2n + (n+1 + k) C (k) ⋅ 2\^(n+1 - k)? There seems to be no apparent solution in that case...

Answer 3

Can anyone show this using induction please?