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.
[Math] Sum of the rows of Pascal’s Triangle.
binomial-coefficients
Related Solutions
There really isn't a closed-form expression for the partial row sums of Pascal's triangle. The expression I imagine you're getting, $$\sum_{k=0}^m \binom{n}{k} = 2^n - \binom{n}{m+1} {}_2F_1(1,m+1-n;m+2;-1),$$ isn't really a closed-form; it's just the original sum expressed differently. (One of the answers to the MO question mentioned above by anon says this as well.)
So, why is this?
(In what follows, the original version contained a partial explanation, as the OP merely wanted hints. Now that the OP has completed the derivation for him/herself, I'm giving the full argument.)
We have $$ \binom{n}{m+1} {}_2F_1(1,m+1-n;m+2;-1) = \binom{n}{m+1} \sum_{k=0}^{\infty} \frac{1^{\overline{k}} (m+1-n)^{\overline{k}} (-1)^k}{(m+2)^{\overline{k}} k!}$$ $$= \binom{n}{m+1} \left[ 1 - \frac{1(m+1-n)}{(m+2)1} + \frac{2!(m+1-n)(m+2-n)}{(m+2)(m+3)2!} \mp \cdots \right]$$ $$= \frac{n!}{(m+1)!(n-m-1)!} \left[ 1 + \frac{n-m-1}{m+2} + \frac{(n-m-1)(n-m-2)}{(m+2)(m+3)} + \cdots \right]$$ $$= \binom{n}{m+1} + \binom{n}{m+2} + \binom{n}{m+3} + \cdots $$ $$= \sum_{k=m+1}^n \binom{n}{k}.$$
Thus $$\sum_{k=0}^m \binom{n}{k} = 2^n - \binom{n}{m+1} {}_2F_1(1,m+1-n;m+2;-1)$$ is just a rewrite of the original sum (together with the fact that $\sum_{k=0}^n\binom{n}{k} = 2^n$).
By the way, Concrete Mathematics spends some time discussing $\sum_{k=0}^m \binom{n}{k}$. On p. 165 they say
"Surely if we can evaluate the corresponding sum with alternating signs, we ought to be able to do this one. But no; there is no closed form for the partial sum of a row of Pascal's triangle."
Then on p. 228 they discuss the sum again, in the context of Gosper's algorithm for finding partial hypergeometric sums. This gives an explanation for why there is no closed-form, as Gosper's algorithm either finds one or proves that no such one exists.
"If we apply the same method to find the indefinite sum $\sum \binom{n}{k} \delta k,$ without the $(-1)^k$, everything will be almost the same except that $q(k)$ will be $n-k$; hence $Q(k) = n-2k$ will have greater degree than $R(k)=n$, and we will conclude that $d$ has the impossible value $\deg(p) - \deg(Q) = -1$. (The polynomial $s(k)$ cannot have negative degree, because it cannot be zero.) Therefore the function $\binom{n}{k}$ is not summable in hypergeometric terms."
However, Exercise 9.42 on p. 492 asks to prove the asymptotic formula $$\sum_{k \leq \alpha n} \binom{n}{k} = 2^{n H(\alpha) - \frac{1}{2} \log_2 n + O(1)},$$ where $H(\alpha) = \alpha \log_2 \frac{1}{\alpha} + (1-\alpha) \log_2 (\frac{1}{1-\alpha})$, for $\alpha \leq \frac{1}{2}$.
There is an outline of the proof of this result in the answer section, so you can look that up if you want to see how they obtain it. See also robjohn's comments below.
If $\alpha \geq \frac{1}{2}$, then $$\sum_{k \leq \alpha n} \binom{n}{k} = 2^{n + O(1)},$$ since the sum is bounded above by $2^n$ and below by $2^{n-1}$.
(Page numbers are for the second edition of Concrete Mathematics.)
It is indeed true that each $x_{n}$ is a product of integers of the form $2^{2^{m}}+1$ (although not of the ones you have stated).
To prove this, we fix an $n\in\mathbb{N}$. Your definition of $x_{n}$ rewrites as $x_{n}=\sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}}2^{i}$.
Write $n$ in the form $n=a_{k}2^{k}+a_{k-1}2^{k-1}+\cdots+a_{0}2^{0}$ for some $k\in\mathbb{N}$ and $a_{0},a_{1},\ldots,a_{k}\in\left\{ 0,1\right\} $. (This is just the base-$2$ representation of $n$, possibly with leading zeroes.)
Lucas's theorem tells you that if $i=b_{k}2^{k}+b_{k-1}2^{k-1}+\cdots+b_{0}2^{0}$ for some $b_{0} ,b_{1},\ldots,b_{k}\in\left\{ 0,1\right\} $, then
$\dbinom{n}{i}\equiv\dbinom{a_{k}}{b_{k}}\dbinom{a_{k-1}}{b_{k-1}} \cdots\dbinom{a_{0}}{b_{0}}=\prod\limits_{j=0}^{k}\underbrace{\dbinom{a_{j}}{b_{j}} }_{\substack{= \begin{cases} 1, & \text{if }b_{j}\leq a_{j}\\ 0, & \text{if }b_{j}>a_{j} \end{cases} \\\text{(since }a_{j}\text{ and }b_{j}\text{ lie in }\left\{ 0,1\right\} \text{)}}}$
$=\prod\limits_{j=0}^{k} \begin{cases} 1, & \text{if }b_{j}\leq a_{j}\\ 0, & \text{if }b_{j}>a_{j} \end{cases} = \begin{cases} 1, & \text{if }b_{j}\leq a_{j}\text{ for all }j\text{;}\\ 0, & \text{otherwise} \end{cases} \mod 2$.
Hence, the $i\in\mathbb{N}$ for which $\dbinom{n}{i}$ is odd are precisely the numbers of the form $b_{k}2^{k}+b_{k-1}2^{k-1} +\cdots+b_{0}2^{0}$ for $b_{0},b_{1},\ldots,b_{k}\in\left\{ 0,1\right\} $ satisfying $\left( b_{j}\leq a_{j}\text{ for all }j\right) $. Since all these $i$ satisfy $i \in \left\{ 0,1,\ldots,n\right\}$ (because otherwise, $\dbinom{n}{i}$ would be $0$ and therefore could not be odd), we can rewrite this as follows: The $i \in \left\{ 0,1,\ldots,n\right\}$ for which $\dbinom{n}{i}$ is odd are precisely the numbers of the form $b_{k}2^{k}+b_{k-1}2^{k-1} +\cdots+b_{0}2^{0}$ for $b_{0},b_{1},\ldots,b_{k}\in\left\{ 0,1\right\} $ satisfying $\left( b_{j}\leq a_{j}\text{ for all }j\right) $. Since these numbers are distinct (because the base-$2$ representation of any $i\in\mathbb{N}$ is unique, as long as we fix the number of digits), we thus can substitute $b_{k}2^{k}+b_{k-1}2^{k-1}+\cdots+b_{0}2^{0}$ for $i$ in the sum $\sum\limits\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\ \dbinom{n}{i}\text{ is odd}}}2^{i}$. Thus, this sum rewrites as follows:
$\sum\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\ \dbinom{n}{i}\text{ is odd}}}2^{i} =\underbrace{\sum\limits_{\substack{b_{0},b_{1} ,\ldots,b_{k}\in\left\{ 0,1\right\} ;\\b_{j}\leq a_{j}\text{ for all }j} }}_{=\sum\limits_{b_{0}=0}^{a_{0}}\sum\limits_{b_{1}=0}^{a_{1}}\cdots\sum\limits_{b_{k}=0}^{a_k} }\underbrace{2^{b_{k}2^{k}+b_{k-1}2^{k-1}+\cdots+b_{0}2^{0}}}_{=\left( 2^{2^{k}}\right) ^{b_{k}}\left( 2^{2^{k-1}}\right) ^{b_{k-1}}\cdots\left( 2^{2^{0}}\right) ^{b_{0}}}$
$=\sum\limits_{b_{0}=0}^{a_{0}}\sum\limits_{b_{1}=0}^{a_{1}}\cdots\sum\limits_{b_{k}=0}^{a_{k} }\left( 2^{2^{k}}\right) ^{b_{k}}\left( 2^{2^{k-1}}\right) ^{b_{k-1} }\cdots\left( 2^{2^{0}}\right) ^{b_{0}}$
$=\left( \sum\limits_{b_{k}=0}^{a_{k}}\left( 2^{2^{k}}\right) ^{b_{k}}\right) \left( \sum\limits_{b_{k-1}=0}^{a_{k-1}}\left( 2^{2^{k-1}}\right) ^{b_{k-1} }\right) \cdots\left( \sum\limits_{b_{0}=0}^{a_{0}}\left( 2^{2^{0}}\right) ^{b_{0}}\right) $
$=\left( \sum\limits_{b=0}^{a_{k}}\left( 2^{2^{k}}\right) ^{b}\right) \left( \sum\limits_{b=0}^{a_{k-1}}\left( 2^{2^{k-1}}\right) ^{b}\right) \cdots\left( \sum\limits_{b=0}^{a_{0}}\left( 2^{2^{0}}\right) ^{b}\right) $
$=\prod\limits_{g=0}^{k}\underbrace{\left( \sum\limits_{b=0}^{a_{g}}\left( 2^{2^{g} }\right) ^{b}\right) }_{\substack{= \begin{cases} 2^{2^{g}}+1, & \text{if }a_{g}=1;\\ 1 & \text{if }a_{g}=0 \end{cases} \\\text{(since }a_{g}\in\left\{ 0,1\right\} \text{)}}}$
$=\prod\limits_{g=0}^{k} \begin{cases} 2^{2^{g}}+1, & \text{if }a_{g}=1;\\ 1 & \text{if }a_{g}=0 \end{cases} $
$=\left( \prod\limits_{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g} =1}}\left( 2^{2^{g}}+1\right) \right) \underbrace{\left( \prod\limits _{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g}=0}}1\right) }_{=1}$
$=\prod\limits_{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g}=1}}\left( 2^{2^{g}}+1\right) $.
Thus, $x_{n}=\sum\limits_{\substack{i\in\left\{ 0,1,\ldots,n\right\} ;\\\dbinom{n}{i}\text{ is odd}}}2^{i}=\prod\limits_{\substack{g\in\left\{ 0,1,\ldots,k\right\} ;\\a_{g}=1}}\left( 2^{2^{g}}+1\right) $. This is clearly a product of Fermat numbers.
EDIT: This result also appears as equation (10) in Andrew Granville, Binomial coefficients modulo prime powers, 1997, where it is ascribed to Larry Roberts.
Best Answer
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
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.