Show $\binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n} = 2^n \space \space \forall n \in \mathbb{N} $ I was requested to show
$$\binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n} = 2^n \space \space \forall n \in \mathbb{N} $$
Since I self study, I have no professor to tell me whether my solution is correct or not. I wonder if anyone could provide some validation. Here is what I did.
$I$. Let $n=1$ and the equality trivially holds.
$II.$ Let our inductive hypothesis $\text{HI}$ be that
$$\sum_{i=0}^k \binom{k}{i} = 2^k$$
Then we want to show
$$\sum_{i=0}^{k+1} \binom{k+1}{i} = 2^{k+1}$$
$III.$
$$
\begin{aligned}
\sum_{i=0}^{k+1} \binom{k+1}{i} 
&= \sum_{i=0}^k \binom{k+1}{i} + \binom{k+1}{k+1}
\\
&= \sum_{i=0}^k \Big(\binom{k}{i-1}+\binom{k}{i}\Big) + 1 
&&\text{By Pascal's triangle formula}
\\
&=\sum_{i=1}^k\binom{k}{i} + \sum_{i=0}^k \binom{k}{i} + 1
\\
&=\sum_{i=0}^k\binom{k}{i} - \binom{k}{0} + 2^k+1 
&&\text{HI}
\\
&=2^k-1+2^k+1
\\
&=2^{k+1}\ ,
\end{aligned}
$$
and thus we have proved what we set out to show.
The two questions I always have when finishing a proof: Is the proof correct? Are there alternative, perhaps simpler proofs? Thanks in advance.
 A: I don't believe the step $$\sum_{i=0}^k\binom{k}{i-1} = \sum_{i=1}^k\binom{k}{i}$$ is justified, although it ends up being true. If you do replace i-1 with i, you should get $$
\begin{align*}
&\sum_{i=0}^k\binom{k}{i-1} \\
&= \sum_{i=-1}^{k-1}\binom{k}{i} \\
&= \sum_{i=0}^{k-1}\binom{k}{i} \\
&= \left(\sum_{i=0}^{k}\binom{k}{i}\right) - \binom{k}{k} \\
&= 2^k - 1
\end{align*}
$$
Also, as the comment mentions, you can do
$$
\begin{align*}
&\sum_{i=0}^k \binom{k}{i} \\
&= \sum_{i=0}^k \binom{k}{i} 1^{n-k}1^k \\
&= (1+1)^k = 2^k
\end{align*}
$$
A: Answer to the first part: there is a slight error between lines 2 and 3 in III part. If you change summation variables via $i \rightarrow i + 1$ the  summation should begin at $i = 0$ and end at $i = k - 1$, not at $i = k$.
Thus it should be
$$
\sum_{i = 0}^k \left( {k \choose i - 1} + {k \choose i} \right) +1 =
\sum_{i = 0}^{k-1}  {k \choose i - 1} +1+\sum_{i = 0}^k{k \choose i}
$$
$$
=\sum_{i = 0}^{k-1}  {k \choose i - 1} +{k \choose k}+\sum_{i = 0}^k{k \choose i}= 2^k + 2^k = 2^{k +1}.
$$
I assumed that ${n \choose -1}= 0$ using definition of a Newton symbol via falling factorial.
Second part: there is a combinatorial interpretation which in this case gives simpler proof. Suppose we have a set of $S$ consisting of $n$ elements and you want to count the number of subsets of $S$.
You can do it in two ways:

*

*Count subsets consisting of $i$ elements, where $i = 0, 1, \dots, n$.
For example there is only one set with zero elements - empty set, ${n \choose 1}$ subsets consisting of exactly one element and so forth.
Total number of subsets is
$$
\sum_{i = 0}^n {n \choose i}.
$$

*For each element $s \in S$ decide if the subset $X \subset S$ contains $s$ or not. For each element you have exactly two choices, so the total number of
different subsets is $2^n$.

Since we counted the same thing in two different ways we obtain that $2^n = \sum_{i = 0}^n {n \choose i}$.
A: If in the binomial formula
$$\big(a+b\big)^n=\sum_\limits{k=0}^n\binom nk a^k b^{n-k}$$
we let $\,a=b=1\,,\;$ we get that
$$2^n=\sum_\limits{k=0}^n\binom nk$$
that is
$$\binom n0+\binom n1+\binom n2+\ldots+\binom nn=2^n$$
