Sum of the rows of Pascal's Triangle. 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. 
 A: 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.
A: 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$.
A: 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}.$$
A: This can also be proven by induction. In order to do so, it is very helpful to prove the following identity:
$$\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}.$$
This can be proven combinatorially, but for the sake of expediency,
\begin{align*}
\binom{n}{k} + \binom{n}{k+1} &= \frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-k-1)!} \\
&= \frac{n!}{k!(n-k)(n-k-1)!} + \frac{n!}{(k+1)k!(n-k-1)!} \\
&= \frac{n!}{k!(n-k-1)!}\left(\frac{1}{n-k} + \frac{1}{k+1}\right) \\
&= \frac{n!}{k!(n-k-1)!}\left(\frac{k+1}{(n-k)(k+1)} + \frac{n - k}{(n-k)(k+1)}\right) \\
&= \frac{n!}{k!(n-k-1)!} \cdot \frac{n+1}{(n-k)(k+1)} \\
&= \frac{(n+1)n!}{(k+1)k!(n-k)(n-k-1)!} \\
&= \frac{(n+1)!}{(k+1)!(n-k)!} \\
&= \binom{n+1}{k+1}.
\end{align*}
Now, let's launch into the induction proof. First, note that $\binom{0}{0} = 1 = 2^0$, so the base case holds.
Next, assume that $\binom{n}{0} + \ldots + \binom{n}{n} = 2^n$. Then, using the identity,
\begin{align*}
&\binom{n+1}{0} + \binom{n+1}{1} + \binom{n+1}{2} + \ldots + \binom{n+1}{n} + \binom{n+1}{n+1} \\
= \, &\binom{n+1}{0} + \left(\binom{n}{0} + \binom{n}{1} \right) + \left(\binom{n}{1} + \binom{n}{2} \right) + \ldots + \left(\binom{n}{n-1} + \binom{n}{n} \right) + \binom{n+1}{n+1}.
\end{align*}
Note that each term of the form $\binom{n}{k}$ where $1 \le k \le n-1$ occurs exactly twice in the above sum. Also, the other terms, $\binom{n+1}{0}, \binom{n}{0}, \binom{n+1}{n+1}, \binom{n}{n}$ are all $1$. Thus we have,
\begin{align*}
&\binom{n+1}{0} + \binom{n+1}{1} + \binom{n+1}{2} + \ldots + \binom{n+1}{n} + \binom{n+1}{n+1} \\
= \, &2\left(\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n-1} + \binom{n}{n} \right) = 2 \cdot 2^n = 2^{n+1}.
\end{align*}
