<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] 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.$$
</s>