# How to prove $\sum_{k\leq n}^{n} \binom{n}{k}= 2^n$ by induction [duplicate]

This question already has an answer here:

$\sum_{k\leq n}^{n} \binom{n}{k}= 2^n , n, k \in \mathbb{N}$

Im trying with mathematical induction but im stuck.

My inductive step:

$H) \sum_{k=0}^{h} \binom{h}{k}= 2^h$

$T) \sum_{k=0}^{h+1} \binom{h+1}{k}= 2^{h+1}$

For the demo:

$\sum_{k=0}^{h+1} \binom{h+1}{k} \Rightarrow \sum_{k=0}^{h} \binom{h}{k} + \sum_{k=0}^{h} \binom{h}{k-1}$

Where i can use the hypothesis in the first term, but dont know how to continue.

## marked as duplicate by Git Gud, Shuchang, user61527, Newb, M TurgeonJan 10 '14 at 0:43

$$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$$ is true for $n\in\mathbb{Z}_{>0}$ and $k\in\mathbb{Z}$.

Here: $$\binom{n}{k}:=0$$ if $k\notin\left\{ 0,\ldots,n\right\}$.

So: $$\sum_{k\in\mathbb{Z}}\binom{n}{k}=\sum_{k\in\mathbb{Z}}\binom{n-1}{k-1}+\sum_{k\in\mathbb{Z}}\binom{n-1}{k}=2^{n-1}+2^{n-1}=2^{n}$$

• Shoot, beat me to it. – Addison Jan 9 '14 at 23:56
• Nice. Is more easy to see in this way. – Wyvern666 Jan 10 '14 at 0:02
• @user84413 Thank you for editing and repairing. I stood up from bed and standing under the shower one of my thoughts was: 'did I write a $k$ or an $n$?... let's check immediately :-). – drhab Jan 10 '14 at 7:50
• @drhab I've had the same experience - I've thought of mistakes I've made like this when I'm brushing my teeth. In any case, nice solution! – user84413 Jan 10 '14 at 17:10

Try using this formula:

$$\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$$

Note this is the reason Pascal's triangle exists.