Prove by induction that $\sum_{r=0}^{n}\binom nr =2^k$

Question

I have to prove by induction that $$\sum_{r=0}^{n}\begin{pmatrix}n \\ r \end{pmatrix}=2^k$$, using the identity $\begin{pmatrix}n \\ r-1 \end{pmatrix}+\begin{pmatrix}n \\ r \end{pmatrix}=\begin{pmatrix}n+1 \\ r \end{pmatrix}$. I'm fine with everything except the inductive step, where I only managed to get as far as $$\sum_{r=0}^{k+1}\begin{pmatrix}n \\ r \end{pmatrix}= \sum_{r=0}^{k}\begin{pmatrix}n \\ r \end{pmatrix}+\begin{pmatrix}n \\ k+1 \end{pmatrix}$$ I tried to then use the identity and substitute $\begin{pmatrix}n \\ r \end{pmatrix}=\begin{pmatrix}n+1 \\ r \end{pmatrix}-\begin{pmatrix}n \\ r-1 \end{pmatrix}$ but all this did was just take me around in a circle. I also couldn't substitute $2^k$ for $\sum_{r=0}^{k}\begin{pmatrix}n \\ r \end{pmatrix}$ since this didn't properly simplify to give $2^{k+1}$. However, I think that I have to obtain the expression $\sum_{r=0}^{k}\begin{pmatrix}n \\ r \end{pmatrix}$ since it simplifies to $2^{k+1}$. But I've not been able to obtain this in anyway so I'm wondering if anyone can guide in what I need to or what direction I need to take to complete the inductive step.

Answer 1

You're mixing up your $n$'s and $k$'s. Where you write:

$$\sum_{r=0}^{k+1}\begin{pmatrix}n \\ r \end{pmatrix}= \sum_{r=0}^{k}\begin{pmatrix}n \\ r \end{pmatrix}+\begin{pmatrix}n \\ k+1 \end{pmatrix}$$

That should be:

$$\sum_{r=0}^{k+1}\begin{pmatrix}{k+1} \\ r \end{pmatrix}= \sum_{r=0}^{k}\begin{pmatrix}{k+1} \\ r \end{pmatrix}+\begin{pmatrix}{k+1} \\ k+1 \end{pmatrix}$$

And the inductive hypothesis is:

$$\sum_{r=0}^{k}\begin{pmatrix}k \\ r \end{pmatrix}=2^k$$

And now when you use Pascal's identity you should be fine.

Answer 2

Assume this is true for base case id est $$2^n=\sum_{r=0}^n{n \choose r}$$So $$2^{n+1}=2\cdot \sum_{r=0}^n{n \choose r}=2\cdot{n \choose 0}+2\cdot{n \choose 1}+...+2\cdot{n \choose n}={n \choose 0}+\left({n \choose 0}+{n \choose 1}\right)+...+\left({n \choose n-1}+{n \choose n}\right)+{n \choose n}$$ Using your identity $${n \choose 0}+{n \choose 1}={n+1 \choose 1}$$ Doing this with every term and noting that ${n \choose 0}={n+1 \choose 0}$ and ${n \choose n}={n+1 \choose n+1}$ gives $$\sum_{r=0}^{n+1}{n+1 \choose r}=2^{n+1}$$

Answer 3

A possible way of writing down the proof is \begin{align} \sum_{i=0}^{n+1} \binom{n+1}{i} &= \sum_{i=0}^{n+1} \left( \binom{n}{i} + \binom{n}{i-1}\right) \\&= \sum_{i=0}^{n} \binom{n}{i} + \sum_{i=1}^{n+1} \binom{n}{i-1} \\&= \sum_{i=0}^{n} \binom{n}{i} + \sum_{j = 0}^{n} \binom{n}{j} \\&= 2^{n} + 2^{n} = 2^{n+1}, \end{align} with the change of variable $j = i - 1$ $$ \sum_{i=1}^{n+1} \binom{n}{i-1} = \sum_{j = 0}^{n} \binom{n}{j}. $$