Closed form solution of a Fibonacci-like recurrence relation

Question

In that case that you have to find the closed form solution for the following recurrence relation, how would you go about approaching it?

$$ g(n) = \begin{cases} b & \text{if} \hspace{0.2cm} n = 0,1 \\ 2g(n-2)+c & \text{otherwise} \end{cases} $$

I have tried

$$ \begin{align*} g(n) &= 2(2g(n-4)+c)+c \\ &= 2(2(2g(n-6)+c)+c)+c \\ &= 2(2(2(2g(n-8)+c)+c)+c)+c \end{align*}$$

but I'm not too sure where to go from there. Any thoughts?

Thanks!

Answer 1

Let $h_n=g(n)+c$. We have $h_0=h_1=b+c$ and $$ g(n) = h_n -c = 2 g(n-2)+c = 2(h_{n-2}-c)+c = 2 h_{n-2} -c $$ from which $h_n= 2 h_{n-2}$ (the inhomogeneous part has been removed through a suitable translation) and by induction $$ h_n = 2^{\left\lfloor\frac{n}{2}\right\rfloor}(b+c), $$ leading to: $$ g(n) = -c+2^{\left\lfloor\frac{n}{2}\right\rfloor}(b+c).$$