Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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}$?
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.
Well, you need to prove the case where $n = k + 1$. According to what you already have, your assumption is in terms of $k$.
