Sum of Sequence of Binomial Coefficients by Powers of 2/Proof 2
Jump to navigation
Jump to search
Theorem
\(\ds \sum_{j \mathop = 0}^n 2^j \binom n j\) | \(=\) | \(\ds \dbinom n 0 + 2 \dbinom n 1 + 2^2 \dbinom n 2 + \dotsb + 2^n \dbinom n n\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 3^n\) |
Proof
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
- $\ds \sum_{j \mathop = 0}^n 2^j \binom n j = 3^n$
$\map P 0$ is the case:
\(\ds \sum_{j \mathop = 0}^0 2^j \binom n j\) | \(=\) | \(\ds \dbinom 0 0\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 3^0\) |
Thus $\map P 0$ is seen to hold.
Basis for the Induction
$\map P 1$ is the case:
\(\ds \sum_{j \mathop = 0}^1 2^j \binom n j\) | \(=\) | \(\ds \dbinom 1 0 + 2 \dbinom 1 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1 + 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 3^1\) |
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
Induction Hypothesis
Now it needs to be shown that if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
- $\ds \sum_{j \mathop = 0}^k 2^j \binom k j = 3^k$
from which it is to be shown that:
- $\ds \sum_{j \mathop = 0}^{k + 1} 2^j \binom {k + 1} j = 3^{k + 1}$
Induction Step
This is the induction step:
\(\ds \sum_{j \mathop = 0}^{k + 1} 2^j \binom {k + 1} j\) | \(=\) | \(\ds \binom {k + 1} 0 + \sum_{j \mathop = 1}^k 2^j \binom {k + 1} j + 2^{k + 1} \dbinom {k + 1} {k + 1}\) | separating out top and bottom indices | |||||||||||
\(\ds \) | \(=\) | \(\ds 1 + \sum_{j \mathop = 1}^k 2^j \binom {k + 1} j + 2^{k + 1}\) | Binomial Coefficient with Zero, Binomial Coefficient with Self | |||||||||||
\(\ds \) | \(=\) | \(\ds 1 + \sum_{j \mathop = 1}^k 2^j \paren {\binom k j + \binom k {j - 1} } + 2^{k + 1}\) | Pascal's Rule | |||||||||||
\(\ds \) | \(=\) | \(\ds 1 + \sum_{j \mathop = 1}^k 2^j \binom k j + 2 \sum_{j \mathop = 1}^k 2^{j - 1} \binom k {j - 1} + 2^{k + 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1 + \sum_{j \mathop = 1}^k 2^j \binom k j + 2 \sum_{j \mathop = 0}^{k - 1} 2^j \binom k j + 2^{k + 1}\) | Translation of Index Variable of Summation | |||||||||||
\(\ds \) | \(=\) | \(\ds 1 + \paren {\sum_{j \mathop = 0}^k 2^j \binom k j - 2^0 \binom k 0} + 2 \paren {\sum_{j \mathop = 0}^k 2^j \binom k j - 2^k \binom k k} + 2^{k + 1}\) | rectifying the end points | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{j \mathop = 0}^k 2^j \binom k j + 2 \sum_{j \mathop = 0}^k 2^j \binom k j - 2 \times 2^k + 2^{k + 1}\) | simplifying | |||||||||||
\(\ds \) | \(=\) | \(\ds 3^k + 2 \times 3^k - 2 \times 2^k + 2^{k + 1}\) | Induction Hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds 3^{k + 1}\) | tidying up |
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\forall n \in \Z_{\ge 0}: \ds \sum_{j \mathop = 0}^n 2^j \binom n j = 3^n$
$\blacksquare$