So you basically want to prove that $$\binom{n}{n}+\binom{n+1}{n}+\binom{n+2}{n}+\dotsc+\binom{n+k}{n}=\binom{n+k+1}{n+1}$$
holds for all $n,k$, right?
Of course you can prove this using induction and Pascal's formula
$$\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}$$
as suggest by Did.
There is a nice combinatorial interpretation of this using double-counting:
Suppose you have $n+1$ eggs, $n$ of them blue and 1 red.
You want to choose $k+1$ of them which is the RHS: $\binom{n+1}{k+1}$
Either you choose the red one in which case you have $\binom{n}{k}$
possibilities for the remaining ones.
Either you don't choose the red one in which case you have $\binom{n}{k+1}$ possibilities for the remaining ones.
Can you think of a similar combinatorial argument which directly works for the original sum?
Hint: Think of $n+k+1$ balls in a row labelled $1,2,\dotsc,n+k+1$. You want to choose $n+1$ of them. That's the RHS: $\binom{n+k+1}{n+1}$.
Now, distinguish cases about which is the rightmost ball you choose. If it's the ball number $n+k+1$ you have $\binom{n+k}{n}$ possibilities to choose the remaining $n$ balls.
If it's the ball number $n+k$ you have $\binom{n+k-1}{n}$ possibilities etc.
Can you complete it from here?
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
Suppose we have Pascal's triangle with $n$ rows, where $n$ is large. From this answer to another question, we have that the proportion of the numbers in the triangle that are less than the central binomial coefficient of row $2k$, is
$$P=2 \left[\mu_0 + \left(\frac{2k}{n}\ln 2\right)^2 \int_{\mu_0}^{1/2} \frac{1}{g(\mu)^2}\mathrm d\mu \right]$$
where $g(\mu)=-\mu\ln \mu-(1-\mu)\ln (1-\mu)$ and $\mu_0=g^{-1}\left(\frac{2k}{n}\ln 2\right)$.
Setting $P=0.5$ and working numerically, we get $k\approx 0.238752608n$ (and $\mu_0\approx 0.10270281182$).
So the median is approximately equal to the central binomial coefficient of row $2k$, where $k\approx0.238752608n$.
The central binomial coefficient of row $2k$ is approximately $\frac{4^k}{\sqrt{\pi k}}$.
So the median is approximately $\dfrac{4^{an}}{\sqrt{\pi an}}$ where $a=0.238752608$.