Finding a closed-form formula for a sequence that is defined recursively

Without any of the usual theoretical tools, you’ll need to do a bit of pattern-recognition. Notice the following pattern:

$$\begin{align*} a_0=0&\\ a_1=1&=2\cdot0+1\\ a_2=1&=2\cdot1-1\\ a_3=3&=2\cdot1+1\\ a_4=5&=2\cdot3-1\\ a_5=11&=2\cdot5+1\\ a_6=21&=2\cdot11-1 \end{align*}$$

This suggests the first-order recurrence $a_n=2a_{n-1}+(-1)^{n-1}$. You can prove by induction that it follows from your second-order recurrence and initial conditions, but let’s hold off on that: it looks like a pretty solid guess, so let’s see what we can do with it. Specifically, we’ll try ‘unwinding’ it:

$$\begin{align*} a_n&=2a_{n-1}+(-1)^{n-1}\\ &=2\left(2a_{n-2}+(-1)^{n-2}\right)+(-1)^{n-1}\\ &=2^2a_{n-2}+2(-1)^{n-2}+(-1)^{n-1}\\ &=2^2\left(2a_{n-3}+(-1)^{n-3}\right)+2(-1)^{n-2}+(-1)^{n-1}\\ &=2^3a_{n-3}+2^2(-1)^{n-3}+2(-1)^{n-2}+(-1)^{n-1}\\ &\;\vdots\\ &=2^ka_{n-k}+\sum_{i=1}^k2^{i-1}(-1)^i\\ &\;\vdots\\ &=2^na_0+\sum_{i=1}^n2^{i-1}(-1)^i\\ &=\sum_{i=1}^n2^{i-1}(-1)^i\;, \end{align*}$$

since $a_0=0$. Finally,

$$\sum_{i=1}^n2^{i-1}(-1)^i=\sum_{i=0}^{n-1}2^i(-1)^{i+1}=-\sum_{i=0}^{n-1}(-2)^i\;,$$

which is just a geometric series, for which you should know a closed form. Once you have that, you should prove by induction that it actually does satisfy your original recurrence.

This ‘unwinding’ technique works surprisingly often with simple first-order recurrences.

One way to do this is to use generating functions.

Let $G(x)=\sum_{n=0}^{\infty}a_nx^n$.

We have the relation : $a_n=a_{n-1}+2a_{n-2}$.

Multiply both sides by $x^n$ and summing from $n=2$ to $\infty$ we get:

$G(x)-a_0-a_1x=x(G(x)-a_0)+2x^2G(x)$.

Then we get: $G(x)(1-x-2x^2)=a_0-a_0x+a_1x=x$ (since $a_0=0,a_1=1$).

So

$\begin{align} G(x)&=\frac{x}{1-x-2x^2} \\ &=\frac{1}{3(1 - 2 z)} - \dfrac{1}{3 (1 + x)} \end{align}$.

We can read off the coeficients of two geometric series:

$\begin{align} a_n &= \frac{1}{3} \cdot 2^n - \frac{1}{3} (-1)^n \\ &= \frac{2^n - (-1)^n}{3} \end{align}$

$a_n = a_{n-1} + 2a_{n-2} \to x^2 - x - 2 = 0 \to (x-2)(x+1) = 0 \to x = 2, -1 \to a_n = A2^n + B(-1)^n$. $a_0 = 0, a_1 = 1\to A+B=0, 2A-B=1 \to A = \dfrac{1}{3}, B = -\dfrac{1}{3} \to a_n = \dfrac{2^n -(-1)^n}{3}$.

Thus: $a_2 = \dfrac{2^2 - (-1)^2}{3} = 1, a_3 = 3, a_4 = 5, a_5 = 11$.