Prove by induction that $\sum_{r=0}^{n}\binom nr =2^k$ 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.
 A: 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.
A: 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}$$
A: 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}.
$$
