$\lim_{n \to \infty} \sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}{\binom{n-k}{k}\frac{1}{2^{n-k}}}$?

Question

Consider the following limit: $$\lim_{n \to \infty} \sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}{\binom{n-k}{k}\frac{1}{2^{n-k}}}.$$ I can find the limit numerically, but is it possible to compute it analytically?

The answer is $\frac{2}{3}$.

Answer 1

Let $a_n$ denote the expression in the limit. Using the identity $n! = \int_{0}^{\infty} x^n e^{-x} \, dx$, we have

\begin{align*} a_n &= \sum_{k=0}^{\lfloor n/2\rfloor} \frac{1}{k!(n-2k)!2^{n-k}} \int_{0}^{\infty} x^{n-k} e^{-x} \, dx \\ &= \int_{0}^{\infty} \underbrace{ \sum_{k=0}^{\lfloor n/2\rfloor} \frac{(x/2)^k}{k!} \frac{(x/2)^{n-2k}}{(n-2k)!} }_{=(\diamond)} e^{-x} \, dx. \end{align*}

The inner sum $(\diamond)$ can be analyzed using the idea of Cauchy product. Indeed, write

$$ (\diamond) = \sum_{\substack{j,k \geq 0 \\ j+2k = n}} \frac{(x/2)^k}{k!} \frac{(x/2)^j}{j!}. $$

Then the generating function for $(a_n)$ is given by

\begin{align*} \sum_{n=0}^{\infty} a_n z^n &= \int_{0}^{\infty} \sum_{n=0}^{\infty} \sum_{\substack{j,k \geq 0 \\ j+2k = n}} \frac{(z^2 x/2)^k}{k!} \frac{(zx/2)^j}{j!} e^{-x} \, dx \\ &= \int_{0}^{\infty} \exp\left( \frac{z^2x}{2} + \frac{zx}{2} - x \right) \, dx \\ &= \frac{1}{1 - \frac{z}{2} - \frac{z^2}{2}} \\ &= \frac{2}{3}\cdot\frac{1}{1-z} + \frac{1}{3}\cdot\frac{1}{1+\frac{z}{2}} \\ &= \sum_{n=0}^{\infty} \frac{2 + \left(-\frac{1}{2}\right)^n}{3} z^n. \end{align*}

Therefore

$$ \lim_{n\to\infty} a_n = \lim_{n\to\infty} \frac{2 + \left(-\frac{1}{2}\right)^n}{3} = \frac{2}{3}. $$

As a sanity check, the following numerical computation confirms the formula $a_n = \frac{2 + \left(-\frac{1}{2}\right)^n}{3}$ derived from above.

$\hspace{2em}$

Answer 2

Someone on 4chan was able to provide a solution.