Challenging limit

$\displaystyle \sum _{ k=0 }^{ n }{ \left( \begin{matrix} n-k \\ k \end{matrix} \right) \dfrac { 1 }{ { 2 }^{ n-k } } }$

generates the series

$\dfrac { 1 }{ 2 } ,\dfrac { 3 }{ 4 } ,\dfrac { 5 }{ 8 } ,\dfrac { 11 }{ 16 } ,\dfrac { 21 }{ 32 } ,\dfrac { 43 }{ 64 } ,\dfrac { 85 }{ 128 } ,...$

where the numerators are Lucas numbers, generated by $2L_{n-2}+L_{n-1}=L_n$ . Thus, the sum can be expressed as

$\dfrac{2^{n+1}-(-1)^{n+1}}{3\cdot2^n}$

which has the limiting value of $\dfrac{2}{3}$ as $n \rightarrow \infty$

This solution assumes that the sum will keep generating the Lucas numbers ad infinitum. Otherswise, prove by induction.

Let $f(n) = \sum_{k=0}^\infty \binom{n-k}{k} \frac1{2^{n-k}}.$ Consider the generating function $\sum_{n=0}^\infty f(n) x^n.$ We get $\sum_{n=0}^\infty f(n) x^n = \sum_{n=0}^\infty \sum_{k=0}^\infty \binom{n-k}{k} \frac1{2^{n-k}} x^n,$ and now we make the substitution $m=n-k$ to get $\begin{aligned} \sum_{n=0}^\infty f(n) x^n &= \sum_{m=0}^\infty \sum_{k=0}^\infty \binom{m}{k} \frac1{2^m} x^{m+k} \\ &= \sum_{m=0}^\infty (x/2)^m \sum_{k=0}^\infty \binom{m}{k} x^k \\ &= \sum_{m=0}^\infty (x/2)^m (1+x)^m \\ &= \frac1{1-\frac{x}2(1+x)} \\ &= \frac2{2-x-x^2} \\ &= \frac23 \left( \frac1{1-x} + \frac1{2+x} \right) \\ &= \frac23 \left( \frac1{1-x} + \frac{1/2}{1+x/2} \right) \\ &= \frac23 \left( \sum_{n=0}^\infty x^n + \frac12 \sum_{n=0}^\infty (-1/2)^n x^n \right), \end{aligned}$ so equating coefficients of $x^n$ gives $f(n) = \frac23 + \frac13 \left( -\frac12 \right)^n,$ which approaches $\frac23$ as $n\to\infty.$