solution to recursive equation $f(n)=2^{n-1}-f(n-1)$

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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