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 Turgeon Jan 10 '14 at 0:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


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

  • $\begingroup$ Shoot, beat me to it. $\endgroup$ – Addison Jan 9 '14 at 23:56
  • $\begingroup$ Nice. Is more easy to see in this way. $\endgroup$ – Wyvern666 Jan 10 '14 at 0:02
  • $\begingroup$ @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 :-). $\endgroup$ – drhab Jan 10 '14 at 7:50
  • $\begingroup$ @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! $\endgroup$ – 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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.