How to prove that $\sum\limits_{k=0}^{n} \binom{n+1}{k+1} = 2^{n+1} - 1$ using the Binomial Theorem?

Question

I have this proposition:

$$\sum_{k=0}^{n} \binom{n+1}{k+1} = 2^{n+1} - 1$$

How can I prove that? How to use the Binomial Theorem to solve that?

Answer 1

Both sides count the number of subset of a set with $n+1$ elements, minus the empty set. Also, the formula could be rewritten as: $$\sum_{k=1}^n\left(\matrix{n\\k}\right) = 2^n -1$$

Answer 2

We obtain

\begin{align*} \sum_{k=0}^n\binom{n+1}{k+1}&=\sum_{k=1}^{n+1}\binom{n+1}{k}\tag{1}\\ &=\sum_{k=0}^{n+1}\binom{n+1}{k}-1\tag{2}\\ &=(1+1)^{n+1}-1\tag{3}\\ &=2^{n+1}-1 \end{align*} and the claim follows.

Comment:

• In (1) we shift the index of the sum by one to start from $k=1$.

• In (2) we add the summand with index $k=0$ and subtract $1$ correspondingly.

• In (3) we apply the binomial theorem.

Answer 3

Use inductive approach

For n = 0: $$\binom{1}{1} = 1 = 2^1 - 1$$ => TRUE

Assume that for n>=0, the following (*) is true $$\sum_{k=0}^{n} \binom{n+1}{k+1} = 2^{n+1} - 1$$

We need prove: $$\sum_{k=0}^{n+1} \binom{n+2}{k+1} = 2^{n+2} - 1$$

Remember: $$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$ So: $$\binom{n+2}{k+1} = \binom{n+1}{k+1} + \binom{n+1}{k}$$

=> $$\sum_{k=0}^{n+1} \binom{n+2}{k+1} = \sum_{k=0}^{n+1}\binom{n+1}{k+1}+\sum_{k=0}^{n+1}\binom{n+1}{k}$$ $$=\binom{n+1}{n+2} + \sum_{k=0}^{n}\binom{n+1}{k+1} + \sum_{k=0}^{n}\binom{n+1}{k+1} - \binom{n+1}{0}$$

$$=2*\sum_{k=0}^{n}\binom{n+1}{k+1} - 1 = 2*2^{n+1} - 1 = 2^{n+2}-1$$

That is what to be proven.