1
$\begingroup$

I've discovered that the sum of each row in Pascal's triangle is $2^n$, where $n$ number of rows. I'm interested why this is so. Rewriting the triangle in terms of C would give us $0C0$ in first row. $1C0$ and $1C1$ in the second, and so on and so forth. However, I still cannot grasp why summing, say, 4C0+4C1+4C2+4c3+4C4=2^4.

$\endgroup$
2
$\begingroup$

If you know the binomial theorem, then it's easy: consider $(1+1)^n$.

If you understand $nCk$ in combinatorial terms as the number of subsets of $k$ elements chosen from a universe of $n$ elements, then it's easy because the total number of subsets is $2^n$.

$\endgroup$
3
$\begingroup$

There are various different ways to look at this. Here's one:

Two adjacent numbers in a row get added to get the number in the row below it: $$ \begin{array}{cccccccccc} & & 1 & & & & & 8 & & & & 28 & & & & 56 & & & & 70 & & \cdots \\ & & & & & & & & \searrow & & \swarrow \\ 1 & & & & & 9 & & & & 36 & & & & 84 & & & & 126 & & \cdots & & & & \cdots \end{array} $$ That means every number in a row is added into the next row twice: $$ \begin{array}{cccccccccc} & & 1 & & & & & 8 & & & & 28 & & & & 56 & & & & 70 & & \cdots \\ & & & & & & \swarrow & & \searrow \\ 1 & & & & & 9 & & & & 36 & & & & 84 & & & & 126 & & \cdots & & & & \cdots \end{array} $$ Since every number is added into the next row twice, the sum of the numbers in the next row is twice as big.

Here's another: In row $9$ (which is the tenth row, since the first row is "row $0$), the entries are. $$ \binom 9 0 = 1,\ \binom 9 1 = 9,\ \binom 9 2 = 36,\ \binom 9 3 = 84,\ \binom 9 4 = 126,\ \ldots $$ These are

  • the number of subsets of size $0$ of a set of size $9$, and
  • the number of subsets of size $1$ of a set of size $9$, and
  • the number of subsets of size $2$ of a set of size $9$, and
  • the number of subsets of size $3$ of a set of size $9$, and
  • and so on.

Their sum is therefore the total number of subsets of a set of size $9$. If you know that that is $2^9$, you've got it.

$\endgroup$
0
$\begingroup$

Use the binomial theorem as:

$$(1+x)^n = {n\choose 0} + {n\choose 1}x^1+ {n\choose 2}x^2+\cdots+{n\choose n}x^n$$ Put $x=1$ to get $$2^n= {n\choose 0} + {n\choose 1}+ {n\choose 2}+\cdots+{n\choose n}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.