0 like 0 dislike
0 like 0 dislike
How can this be proven?

3 Answers

0 like 0 dislike
0 like 0 dislike
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.
0 like 0 dislike
0 like 0 dislike
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...
0 like 0 dislike
0 like 0 dislike
Can anyone show this using induction please?

No related questions found

24.8k questions

103k answers

0 comments

33.7k users

OhhAskMe is a math solving hub where high school and university students ask and answer loads of math questions, discuss the latest in math, and share their knowledge. It’s 100% free!