Sum of Entries in Row of Pascal's Triangle

From ProofWiki
Jump to navigation Jump to search

Theorem

The sum of all the entries in the $n$th row of Pascal's triangle is equal to $2^n$.


Proof 1

By definition, the entries in $n$th row of Pascal's triangle are exactly the binomial coefficients:

$\dbinom n 0, \dbinom n 1, \ldots, \dbinom n n$

The result follows from Sum of Binomial Coefficients over Lower Index.

$\blacksquare$


Proof 2

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$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_of_Entries_in_Row_of_Pascal%27s_Triangle&oldid=511469"