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

Solution 1:

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