<s>[INST] solution to recursive equation $f(n)=2^{n-1}-f(n-1)$ how do I solve this recursive equation:
$f(n)=2^{n-1}-f(n-1)$ when $f(0)=1$
I tried the iteration method but got to a series with changing +/- signs which I had hard time solve.
 [/INST] One approach via generating functions:
$$\begin{align}
G(x) &= \sum_{n=0}^{\infty} f(n) x^n \\
 &= 1x^0 + \sum_{n=1}^{\infty} f(n) x^n \\
 &= 1 + \sum_{n=1}^{\infty} 2^{n-1}x^n-\sum_{n=1}^{\infty}f(n-1) x^n \\
 &= 1 + x\sum_{n=0}^{\infty} 2^{n}x^n-x\sum_{n=0}^{\infty}f(n) x^{n}  \\
 &= 1 + \frac{x}{1-2x}-xG(x) \\ 
 &= \frac{x - 1}{2 x^2 + x - 1} \\
 &= \frac{2}{3} \cdot \frac{1}{1 + x} + \frac{1}{3} \cdot \frac{1}{1 - 2 x}\end{align}$$
Implying:
$$f(n) = \frac{2}{3} \cdot (-1)^n + \frac{1}{3} \cdot 2^n$$
</s>