# Can't find an identity for proving that $\sum_{k=0}^{i+1} \binom {i+1} k=2^{i+1}$ [duplicate]

$$\sum_{k=0}^{i+1} \binom {i+1} k$$

I can't find an identity for this summation :(

To clarify I'm trying to prove using induction that this sum is equal to $2^{i+1}$, I have my basis and inductive hypothesis done, this is just my inductive step

• Your question is not very clear. Would you perhaps care to elucidate what you mean? Mar 30, 2014 at 4:55
• The sum is $2^{i+1}$ by binomial theorem. Why do you need an inequality for this? Mar 30, 2014 at 4:57
• $\sum_{k=0}^{i+1} \binom{i+1}{k} < \infty$. There you go Mar 30, 2014 at 4:57
• Clarified my question above Mar 30, 2014 at 5:00
• Using Pascal's identity, you can split the sum $\sum_{k=0}^{i+1}\binom{i+1}{k}$ into two copies of $\sum_{k=0}^i\binom{i}{k}$. In the induction step, you assume the second sum is $2^i$, this immediately implies the first sum is $2\times2^i = 2^{i+1}$. You should work out the Pascal's identity for the first few $i$, everything will then become obvious. Mar 30, 2014 at 5:26

Your problem can be proved without making direct application of the Binomial Theorem itself. Let us consider two disjoint sets $A$ and $B$ and $n$ elements at our disposal. Now the problem is to divide the $n$ elements in the two sets. In how many ways can it be done? The answer is easy.
First analyze the problem as for any one of the $n$ elements there are two possibilities of satisfying the condition, namely , either it goes into $A$ or into $B$. It is easy to see that the total number of ways in this case is indeed $2^n$. Right?
Now analyze the same problem a bit differently. Since the sets are disjoint, if we can analyze all the possible distributions in $A$, it will automatically determine all the possible distribution in $B$ because there is a one-one correspondence between the distributions in $A$ and that in $B$. We can take $0$ elements from $n$ elements, the number of ways of choosing in such a manner being $\binom {n}{0}$. Similarly when we choose $1$ element the number of ways becomes $\binom {n}{1}$ and thus generalizing if we choose $i (\leq n)$ elements the number of ways becomes $\binom {n}{i}$ and since each such choice is mutually exclusive with any other choice the total number of such choices will be $\sum_{i=0}^{n} \binom {n}{i}$. And since the total number of ways must be unique we get $\sum_{i=0}^{n} \binom {n}{i}=2^n$. Hence proved.