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

Solution 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.

Solution 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}$$