Sum of Sequence of Binomial Coefficients by Powers of 2

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z$ be an integer.


Then:

\(\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 1

\(\ds 3^n\) \(=\) \(\ds \paren {2 + 1}^n\)
\(\ds \) \(=\) \(\ds \sum_{j \mathop = 0}^n 2^j 1^{n - j} \binom n j\) Binomial Theorem
\(\ds \) \(=\) \(\ds \sum_{j \mathop = 0}^n 2^j \binom n j\)

$\blacksquare$


Proof 2

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$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_of_Sequence_of_Binomial_Coefficients_by_Powers_of_2&oldid=465055"