Induction proof using Pascal's Identity: $\binom{n}{0}+\binom{n}{i}+....+\binom{n}{n}=2^n$

Question

Prove by induction that for all $n ≥ 0$:

$\binom{n}{0}+\binom{n}{i}+....+\binom{n}{n}=2^n$

We should use pascal's identity

Base case: $n=0$

LHS: $\binom{0}{0}=1$

RHS: $2^0=1$

Inductive step: Here is where I am get held up. I know Pascal's Identity $\displaystyle\binom{n+1}{k+1}=\binom nk+\binom n{k+1}$ and I am looking to prove $n+1$

so do I want to prove : $\binom{k}{0}+\binom{k}{1}+....+\binom{k}{k}+\binom{n+1}{k+1}=2^{k+1}$?

Answer 1

Your induction hypothesis is that

$$\binom{n}0+\binom{n}1+\ldots+\binom{n}n=2^n\;,$$

and you want to prove that

$$\binom{n+1}0+\binom{n+1}1+\ldots+\binom{n+1}{n+1}=2^{n+1}\;.$$

Pascal’s identity allows you to write

$$\begin{align*}\binom{n+1}1&+\binom{n+1}2+\ldots+\binom{n+1}n\\ &=\left(\binom{n}0+\binom{n}1\right)+\left(\binom{n}1+\binom{n}2\right)+\ldots+\left(\binom{n}{n-1}+\binom{n}n\right)\\ &=\binom{n}0+2\binom{n}1+2\binom{n}2+\ldots+2\binom{n}{n-1}+\binom{n}n\;, \end{align*}$$

and $\dbinom{n+1}0=\dbinom{n+1}{n+1}=1$, so

$$\begin{align*}\binom{n+1}0&+\binom{n+1}1+\ldots+\binom{n+1}{n+1}\\ &=1+\binom{n}0+2\binom{n}1+2\binom{n}2+\ldots+2\binom{n}{n-1}+\binom{n}n+1\\ &=2\binom{n}0+2\binom{n}1+2\binom{n}2+\ldots+2\binom{n}{n-1}+2\binom{n}n\;. \end{align*}$$

And at that point you’re almost done.

Answer 2

Well, you need to prove the case where $n = k + 1$. According to what you already have, your assumption is in terms of $k$.