Sum of Entries in Row of Pascal's Triangle/Proof 2
Theorem
The sum of all the entries in the $n$th row of Pascal's triangle is equal to $2^n$.
Proof
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
- The sum of all the entries in the $n$th row of Pascal's triangle is equal to $2^n$.
Basis for the Induction
$\map P 0$ is the case:
- The sum of all the entries in the row $0$ of Pascal's triangle is equal to $2^0 = 1$.
This is true, as the only non-zero entry in row $0$ is $\dbinom 0 0$ which equals $1$.
Thus $\map P 0$ 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 0$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
- The sum of all the entries in the row $k$ of Pascal's triangle is equal to $2^k$.
from which it is to be shown that:
- The sum of all the entries in the row $k + 1$ of Pascal's triangle is equal to $2^{k + 1}$.
Induction Step
This is the induction step:
In row $k + 1$ there are $k + 2$ entries:
- $\dbinom {k + 1} 0, \dbinom {k + 1} 1, \dbinom {k + 1} 2, \ldots, \dbinom {k + 1} k, \dbinom {k + 1} {k + 1}$
From Pascal's Rule:
- $\dbinom {k + 1} j = \dbinom k {j - 1} + \dbinom k j$
Thus for each of the $k + 1$ entries in row $k$:
- $\dbinom k 0, \dbinom k 1, \ldots, \dbinom k k$
Element $\dbinom k j$ contributes to exactly $2$ elements of row $k + 1$
- $\dbinom {k + 1} j$ and $\dbinom {k + 1} {j + 1}$
So the sum of all the elements of row $k + 1$ is equal to $2$ times the sum of all the elements of row $k$.
By the induction hypothesis, that means the sum of all the elements of row $k + 1$ is equal to $2 \times 2^k$.
That is, the sum of all the entries in the row $k + 1$ of Pascal's triangle is equal to $2^{k + 1}$.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- For all $n \in \Z_{\ge 0}$, the sum of all the entries in the $n$th row of Pascal's triangle is equal to $2^n$.
$\blacksquare$