Solve a recurrence that has two forms for $n$ even or odd

Question

I am very new to recurrence, I became able to solve the most basic once.

But now I found one that has a different form, depending on n if it is even or odd:

the base case a(0) is 0.

for $n$ even: $a(n) = 2a(n-1) + 2^{n+1}$

for $n$ odd: $a(n) = 2a(n-1) + 2^{n}$

I don't even know how to start, I was able to compute some values maybe I would see a pattern but I don't know how to go further.

Answer 1

You can combine them into one recurrence for just the even terms. For $n$ even we have $n-1$ is odd, so we can write $$a(n)=2a(n-1)+2^{n+1}\\ a(n-1)=2a(n-2)+2^{n-1}\\ a(n)=4a(n-2)+3\cdot 2^{n}$$ Solve this recurrence to get the even terms, then apply the odd recurrence to the formula to get the odd terms. If it makes it easier for you, you can define $m=\frac n2$ and write the recurrence in terms of $m$ to get the term on the right to be the $(m-1)^{st}$ term.