Sum of binomial numbers

Task number: 3315

Without using the meaning of or formula for a binomial coefficient, only using the fact

\(\displaystyle\binom{0}{0}=1\), \(\displaystyle\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}\) a \(\displaystyle\binom{n}{k}=0\) když \(k<0\) nebo \(k>n\)

prove that:

\( \displaystyle\sum_{k=0}^n\binom{n}{k}=2^n \)

  • Solution

    For \(n=0\):
    \(\displaystyle\sum_{k=0}^0\binom{0}{k}=\binom{0}{0}= 1 = 2^0\).

    Induction step \(n \to n+1\):
    \(\displaystyle\sum_{k=0}^{n+1}\binom{n+1}{k}= \sum_{k=-1}^{n}\binom{n+1}{k+1}= \sum_{k=-1}^{n}\left[\binom{n}{k}+\binom{n}{k+1}\right]= \sum_{k=-1}^{n}\binom{n}{k}+ \sum_{k=-1}^{n}\binom{n}{k+1}=\\ \displaystyle=\binom{n}{-1}+ \sum_{k=0}^{n}\binom{n}{k}+ \sum_{k=0}^{n}\binom{n}{k}+ \binom{n}{n+1} =0+2^n+2^n+0 =2^{n+1}\).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email