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

Question

$\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.

score 4 · Accepted Answer · edited Jan 10 '14 at 00:38

4

$$\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}$$

edited Jan 10 '14 at 00:38

user84413

answered Jan 09 '14 at 23:52

drhab

Shoot, beat me to it. – Addison Jan 09 '14 at 23:56
Nice. Is more easy to see in this way. – Wyvern666 Jan 10 '14 at 00: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 07: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

score 0 · Answer 2 · answered Jan 09 '14 at 23:55

0

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.

answered Jan 09 '14 at 23:55

Addison

2 Answers2