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.
 A: Hint:
$$f(n-1)+f(n)=2^{n-1}$$
$$f(n)+f(n+1)=2^n$$
Subtracting,
$$f(n+1)-f(n-1)=2^{n-1}.$$
This reduces to an easier recurrence to deal with (as the series has no $\pm$ signs). Can you solve it from here, using that $f(0)=1$ and $f(1)=0$?
A: 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$$
A: $$f(0)=1$$
$$f(1)=2^0-1$$
$$f(2)=2^1-2^0+1$$
$$f(3)=2^2-2^1+2^0-1$$
$$f(4)=2^3-2^2+2^1-2^0+1$$
It seems that:
$$f(n)=\sum_{k=0}^{n-1}\left((-1)^k2^{n-1-k}\right)+(-1)^n$$
From here you could simplify the geometric sum into an exponential expression in $n$, simplify, and verify that the result satisfies the recurrence and initial condition.
A: $$f(n) + f(n-1) = 2^{n-1}$$
$$f(n-1) + f(n-2) = 2^{n-2}$$
Dividing first by second, we get
$$ \frac{f(n) + f(n-1)}{f(n-1) + f(n-2)}= 2$$
$$\implies f(n) = f(n-1) + 2f(n-2)$$
Now this is in the form of a standard recurrence and should be easy to solve. 
