$\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.
 A: In trying to evaluate
$$\sum_{k=0}^{n-1} {n-1-k\choose k} \frac{1}{2^{n-1-k}}
+ \sum_{k=0}^{n-2} {n-2-k\choose k} \frac{1}{2^{n-2-k}}$$
we introduce
$$S_n = \sum_{k=0}^n {n-k\choose k} \frac{1}{2^{n-k}}$$
which is
$$\frac{1}{2^n} \sum_{k=0}^n {n-k\choose n-2k} 2^k
= \frac{1}{2^n} [z^n] (1+z)^n
\sum_{k\ge 0} \frac{z^{2k}}{(1+z)^k} 2^k.$$
Here we have extended the sum to infinity because the coefficient
extractor enforces the upper limit. Even more, it enforces $n\ge 2k.$
Continuing,
$$\frac{1}{2^n} [z^n] (1+z)^n
\frac{1}{1-2z^2/(1+z)}
\\ = \frac{1}{2^n}
\; \underset{z}{\mathrm{res}} \;
\frac{1}{z^{n+1}} (1+z)^{n+1}
\frac{1}{1+z-2z^2}.$$
Now we put $z/(1+z) = w$ so that $z = w/(1-w)$ and $dz = 1/(1-w)^2 \;
dw$ to get
$$\frac{1}{2^n}
\; \underset{w}{\mathrm{res}} \;
\frac{1}{w^{n+1}}
\frac{1}{1+w/(1-w)-2w^2/(1-w)^2}
\frac{1}{(1-w)^2}
\\ = \frac{1}{2^n}
\; \underset{w}{\mathrm{res}} \;
\frac{1}{w^{n+1}}
\frac{1}{(1-w)^2+w(1-w)-2w^2}
\\ = \frac{1}{2^n}
\; \underset{w}{\mathrm{res}} \;
\frac{1}{w^{n+1}}
\frac{1}{1-w-2w^2}.$$
We have
$$\frac{1}{1-w-2w^2}
= \frac{1}{3} \left[\frac{1}{1+w} + \frac{2}{1-2w}\right]$$
so that extracting the coefficient we find
$$ S_n = \frac{1}{2^n \times 3} [ (-1)^n + 2^{n+1} ]$$
or alternatively
$$\bbox[5px,border:2px solid #00A000]{
S_n = \frac{1}{3} \left(-\frac{1}{2}\right)^n
+ \frac{2}{3}.}$$
We also have
$$S_{n-1} + S_{n-2}
= \frac{1}{3} \left(-\frac{1}{2}\right)^{n-2}
\left(1-\frac{1}{2}\right)
+ \frac{4}{3}
= - \frac{1}{3} \left(-\frac{1}{2}\right)^{n-1}
+ \frac{4}{3} = 2 S_n.$$
A: Let $$a_m=\sum_{k=0}^{m/2} \binom{m-k}{k}\left(\frac{1}{2}\right)^{m-k}$$ so that your desired expression is $a_{n-1}+a_{n-2}$.  We show that $a_m=(2+(-2)^{-m})/3$, yielding $a_{n-1}+a_{n-2}=2(2+(-2)^{-n})/3$.
Let $A(z)=\sum_{m=0}^\infty a_m z^m$ be the ordinary generating function.  Then
\begin{align}
A(z) &= \sum_{m=0}^\infty \left(\sum_{k=0}^{m/2} \binom{m-k}{k}\left(\frac{1}{2}\right)^{m-k}\right) z^m \\
&= \sum_{k=0}^\infty 2^k \sum_{m=2k}^\infty \binom{m-k}{k} (z/2)^m \\
&= \sum_{k=0}^\infty 2^k (z/2)^{2k} \sum_{m=0}^\infty \binom{m+k}{k} (z/2)^m \\
&= \sum_{k=0}^\infty (z^2/2)^k \frac{1}{(1-z/2)^{k+1}} \\
&= \frac{1}{1-z/2}\sum_{k=0}^\infty \left(\frac{z^2/2}{1-z/2}\right)^k \\
&= \frac{1}{1-z/2}\sum_{k=0}^\infty \left(\frac{z^2}{2-z}\right)^k \\
&= \frac{1}{1-z/2}\cdot\frac{1}{1-z^2/(2-z)} \\
&= \frac{2}{(1-z)(2+z)} \\
&= \frac{2/3}{1-z}+\frac{2/3}{2+z} \\
&= \frac{2/3}{1-z}+\frac{1/3}{1+z/2} \\
&= \frac{2}{3}\sum_{m=0}^\infty z^m + \frac{1}{3}\sum_{m=0}^\infty (-z/2)^m \\
&= \sum_{m=0}^\infty \frac{2+(-2)^{-m}}{3} z^m,
\end{align}
so $a_m=(2+(-2)^{-m})/3$.
A: 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.
