<s>[INST] $\sum_{k=0}^{n-1} {n-1-k\choose k}\left(\frac{1}{2}\right)^{n-1-k}+\sum_{k=0}^{n-2} {n-2-k\choose k}\left(\frac{1}{2}\right)^{n-2-k} $ How can you find
$$
\sum_{k=0}^{n-1} {n-1-k\choose k}\left(\frac{1}{2}\right)^{n-1-k}+\sum_{k=0}^{n-2} {n-2-k\choose k}\left(\frac{1}{2}\right)^{n-2-k}
$$
?
I found the value via interpritting the above formula combinatorially. (If I am correct, it is $\frac{2}{3}+\frac{1}{3}\left(-\frac{1}{2}\right)^n$)
But I want to know how to solve it by way of complex integrals or formal power series or any algebraic manipulations.
 [/INST] We will consider the generating function
$$F_n(x)=\sum_{k=0}^\infty \binom{n-k}{k} x^k$$
Note that since $\binom{n-k}{k}=\binom{n-k-1}{k-1}+\binom{n-k-1}{k}$, we can multiply both sides by $x^k$ and sum from $k=0$ to $\infty$ to get
$$F_n(x)=xF_{n-2}(x)+F_{n-1}(x)$$
$$F_n(x)-F_{n-1}(x)-xF_{n-2}(x)=0$$
We can solve this linear recursion to get that
$$F_n(x)=\left(\frac{1+\sqrt{1+4x}}{2}\right)^nA(x)+\left(\frac{1-\sqrt{1+4x}}{2}\right)^nB(x)$$
For some functions $A(x)$ and $B(x)$. We can verify that $F_0(x)=1$ and $F_1(x)=1$, so we get the following system
$$\begin{cases}1=A(x)+B(x)\\ 
1=\left(\frac{1+\sqrt{1+4x}}{2}\right)A(x)+\left(\frac{1-\sqrt{1+4x}}{2}\right)B(x)\end{cases}$$
$$\begin{cases}1=A(x)+B(x)\\ 
2=(1+\sqrt{1+4x})A(x)+(1-\sqrt{1+4x})B(x)\end{cases}$$
$$\begin{cases}1=A(x)+B(x)\\ 
1=\sqrt{1+4x}A(x)-\sqrt{1+4x}B(x)\end{cases}$$
$$\begin{cases}1=A(x)+B(x)\\ 
\frac{1}{\sqrt{1+4x}}=A(x)-B(x)\end{cases}$$
$$\begin{cases}\frac{1+\sqrt{1+4x}}{2\sqrt{1+4x}}=A(x)\\ 
\frac{-1+\sqrt{1+4x}}{2\sqrt{1+4x}}=B(x)\end{cases}$$
Our desired sum is the value of
$$\frac{F_{n-1}(2)}{2^{n-1}}+\frac{F_{n-2}(2)}{2^{n-2}}$$
From our recursive definition of $F_n(x)$, we get that this is equivalent to
$$\frac{F_n(2)}{2^{n-1}}$$
We can use our explicit formula for $F_n(x)$, to get that this is
$$\frac{\left(\frac{1+\sqrt{1+8}}{2}\right)^nA(2)+\left(\frac{1-\sqrt{1+8}}{2}\right)^nB(2)}{2^{n-1}}$$
$$=\frac{(2)^nA(2)+(-1)^nB(2)}{2^{n-1}}$$
$$=\frac{\frac{2^{n+1}}{3}+\frac{(-1)^n}{3}}{2^{n-1}}$$
$$=\frac{4}{3}-\frac{1}{3}\left(-\frac{1}{2}\right)^{n-1}$$
This result (verified computationally) is double the result you found.
</s>