Find $\lim_{n\to\infty} \sqrt[n]{a_n}$ where $a_n=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}$ Let $a_n=\sum_{k=0}^{[n/2]} C_{n-k}^k$. Find $\lim_{n\to\infty} \sqrt[n]{a_n}$. Here $[n/2]$ is the largest integer $\leq n/2$, $C_{n-k}^k=\frac{(n-k)!}{k!(n-2k)!}$.
It sounds $a_{2m+1}-a_{2m}=a_{2m-1}$. Then...
 A: We have the following lemma which follows from a stronger inequality proven in this question:

If $(a_n)$ is a sequence in $\mathbb{R}^+$ and $\lim_{n\to\infty}\frac{a_{n+1}}{a_n}$ exists then
  $$\lim_{n\to\infty}\sqrt[n]{a_n}=\lim_{n\to\infty}\frac{a_{n+1}}{a_n}$$

For this sequence we have that
$$a_{2n+1}=a_{2n}+a_{2n-1}$$
$$\frac{a_{2n+1}}{a_{2n}}=1+\frac{a_{2n-1}}{a_{2n}}\tag{1}$$
Also, by taking $n\to\infty$, we have that 
$$\lim_{n\to\infty}\frac{a_{n+1}}{a_n}=\lim_{n\to\infty}\frac{a_{2n+1}}{a_{2n}}=\lim_{n\to\infty}\frac{a_{2n}}{a_{2n-1}}\tag{2}$$
Hence if we denote the desired limit by
$$\lim_{n\to\infty}\sqrt[n]{a_n}=\lim_{n\to\infty}\frac{a_{n+1}}{a_n}=L$$
then, using $(1)$ and $(2)$, we get the equation
$$L=1+\frac1{L}$$
which we can solve for $L\gt0$ giving
$$\boxed{\lim_{n\to\infty}\sqrt[n]{a_n}=\frac{\sqrt{5}+1}2}$$
A: Clearly,
$$
\max_{0\le k\le\frac{n}{2} }C_k^{n-k}\le a_n=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} C_k^{n-k}\le \frac{n}{2}\max_{0\le k\le\frac{n}{2} }C_k^{n-k}
$$
Hence if we show that $$\left(\max_{0\le k\le\frac{n}{2} }C_k^{n-k}\right)^{1/n}\to L,$$
then we shall have that $a_n^{1/n}\to L$.
Next observe that 
$$
C_k^{n-k}=\frac{(n-2k)(n-2k+1)}{k(n-k)}\cdot C_{k-1}^{n-k+1}
$$
and hence
$C_k^{n-k}$ is maximised (for fixed $n$) asymptotically when $k=\dfrac{(5-\sqrt{5})n}{10}$. So
$$
\max_{0\le k\le\frac{n}{2} }C_k^{n-k}\approx \frac{((1-c)n)!}{(cn)!((1-2c)n)!}, \quad c=\dfrac{5-\sqrt{5}}{10}.
$$
Next we use that fact that
$\dfrac{(n!)^{1/n}}{n}\to\dfrac{1}{\mathrm{e}}$
Hence
$$
\left(\frac{((1-c)n)!}{(cn)!((1-2c)n)!}\right)^{1/n}=
\left(\frac{\frac{((1-c)n)!}{((1-c)n)^{(1-c)n}}}{\frac{(cn)!}{(cn)^{cn}}\frac{((1-2c)n)!}{((1-2c)n)^{(1-2c)n}}}\right)^{1/n}\cdot \frac{(1-c)^{1-c}}{c^c(1-2c)^{1-2c}}\to \frac{(1-c)^{1-c}}{c^c(1-2c)^{1-2c}}.
$$
A: How about schematically:
$a_n =$ the sum of the first half of the nth row of pascal's triangle
= half of 2^n when n is odd and a bit more than that when n is even
= roughly $2^{(n-1)}$
Hence the nth root of this is $2^{(1-1/n)}$ which tends to 2 as n-> inf
