<s>[INST] Find limit of formula with binomial coefficcients The Problem
Given:
$$f(n) = \frac{\sum_{i=1}^{n/2} \left[ \binom{n/2}{i} \sum_{j=0}^{i} \binom{n/2}{j} \right]}{2^n}$$
I want to prove that $\lim_{n \rightarrow \infty}f(n) = \frac{1}{2}$.
This relates to some research work I am doing and I am pretty sure it converges to $1/2$ from 'above' (or at least the data suggests that) but I would really like to have some solid proof about this limit.
What I've tried
I've tried to sandwich the limit by substituting the term $\sum_{j=0}^{i} \binom{n/2}{j}$ with a minimum value, i.e. $\binom{n/2}{0}+\binom{n/2}{1}=1+\frac{n}{2}$ (common to all subterms), which leads to $\lim_{n \rightarrow \infty}f(n) = 0$ and with a maximum value, i.e. $\sum_{j=0}^{n/2} \binom{n/2}{j}=2^{n/2}$ (adding extra subterms), which leads to $\lim_{n \rightarrow \infty}f(n) = 1$, but well, I need something better :) I've tried using the some other related formulas but couldn't find something better than that. Maybe it can be solved more straightforward though?
 [/INST] Let $m=n/2$ for ease of notation and let a symbol $\mathbf x$ in bold denote $\binom mx$. Let's write out the numerator for $m=4$:
$$\begin{align}&\mathbf{1(0+1)}+\\
&\mathbf{2(0+1+2)}+\\
&\mathbf{3(0+1+2+3)}+\\
&\mathbf{4(0+1+2+3+4)}
\end{align}$$
By the symmetry of binomial coefficients, the above expression is equal to
$$\begin{align}\mathbf{(0+1+2+3+4)0}&\\
+\mathbf{(1+2+3+4)1}&\\
+\mathbf{(2+3+4)2}&\\
+\mathbf{(3+4)3}&
\end{align}$$
If we add the two together we get
$$\begin{align}
&\mathbf{0(0+1+2+3+4)}+\\
&\mathbf{1(0+1+2+3+4+1)}+\\
&\mathbf{2(0+1+2+3+4+2)}+\\
&\mathbf{3(0+1+2+3+4+3)}+\\
&\mathbf{4(0+1+2+3+4)}
\end{align}$$
$$=(\mathbf{0+1+2+3+4})^2+\mathbf 1^2+\mathbf 2^2+\mathbf 3^2=2^{2×4}+\mathbf 1^2+\mathbf 2^2+\mathbf 3^2$$
It is easy enough to derive the generalisation:
$$f(m)=\frac{(1/2)(2^{2m}+\sum_{k=1}^{m-1}\mathbf k^2)}{2^{2m}}$$
As $n\to\infty$ (and hence $m\to\infty$ too), $\sum_{k=1}^{m-1}\mathbf k^2$ does not grow as fast as $2^{2m}$ – it is smaller by a factor of $\sqrt{\pi m}$ – so it becomes negligible:
$$\lim_{m\to\infty}f(m)=\lim_{m\to\infty}\frac{(1/2)2^{2m}}{2^{2m}}=\frac12$$
</s>