$\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.

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$.
