I am trying to prove a formula by induction but I cant get it right. Something is wrong somewhere and I dont know where. Any help will be greatly appreciated.
We want to use induction to prove that: $$\sum_{k=0}^n {n \choose k} = 2^n$$ Base Case 1: When n = 0 $$ {0 \choose 0} = 2^0 $$ Base Case 2: When n = 1 $${1 \choose 0} + { 1 \choose 1} = 2 ^ 1$$ Lets assume that the equation is true for $p < n$ where p$ >= 1$ Then the equation is true for $p - 1$ $$\sum_{k=0}^{p-1}{p-1 \choose k} = 2^{p-1}$$ $${p-1 \choose 0} + \sum_{k=1}^{p-1}{p-1 \choose k} = 2^{p-1}$$ $$\sum_{k=1}^{p-1}{p-1 \choose k} = 2^{p-1} - 1$$ Also $$\sum_{{k - 1=0}}^{p-1}{p-1 \choose k-1} = 2^{p-1}$$ $$\sum_{k = 1}^{p-1}{p-1 \choose k-1} = 2^{p-1}$$ When we add these two equations we get: $$\sum_{k=1}^{p-1}{p-1 \choose k} + \sum_{k = 1}^{p-1}{p-1 \choose k-1} = 2^{p-1} - 1 + 2^{p-1}$$ $$\sum_{k=1}^{p-1}{p-1 \choose k} + \sum_{k = 1}^{p-1}{p-1 \choose k-1} = 2^p - 1$$ $$\sum_{k=1}^{p-1}{({p-1 \choose k} + {p-1 \choose k-1})} = 2^p - 1$$ $$\sum_{k=1}^{p-1}{p \choose k} = 2^p - 1$$ This is where I get stuck. I can't convert it to $$\sum_{k=0}^{p}{p \choose k} = 2^p $$
$$\sum_{k = 1}^{p-1}{p-1 \choose k-1} = 2^{p-1}$$ is not correct. It should be $$\sum_{k = 1}^{p}{p-1 \choose k-1} = 2^{p-1}$$.
$ \sum\limits_{k=1}^{p-1} \binom {p} {k}=\binom {p} {1}+\binom {p} {2}+...+\binom {p} {p-1}$ and $ \sum\limits_{k=0}^{p} \binom {p} {k}=\binom {p} {0}+\binom {p} {1}+...+\binom {p} {p}$. What differences do you find between these two sums? If you remember that $\binom {p} {0}=\binom {p} {p } (=1)$ then you can complete your argument.