Find the explicit formula for the sequence $a_n$ that's defined by recurrence relation $a_{n+2}=a_{n+1}+2a_n$ and $a_0=a_1=1$

Question

I'm doing math by doing practice problems in my textbook.

I was able to find the explicit formula for $a_n$ such that $a_{n+1}=a_n+2^n$ (which is $2^k-1$) I understand the theorems, but I'm having trouble solving questions.

I'm stuck on the second problem already. How do I find the explicit formula for the sequence $a_n$ that's defined by recurrence relation $a_{n+2}=a_{n+1}+2a_n$ and $a_0=a_1=1$? First of all, how do I even find a generating function?

Answer 1

Say we have a generating function $g(x) = \displaystyle \sum_{n=0}^\infty a_n x^n$ for $a_n$.

Then $g(x) = \displaystyle 1 + x + \sum_{n=2}^\infty (a_{n-1} + 2a_{n-2})x^n = 1 + x + \sum_{n=2}^\infty a_{n-1}x^n + 2\sum_{n=2}^\infty a_{n-2}x^n$

But we have that $\displaystyle \sum_{n=2}^\infty a_{n-1}x^n = x \sum_{n=2}^\infty a_{n-1} x^{n-1} = x(g(x) - 1)$, and similarly, $\displaystyle \sum_{n=2}^\infty a_{n-2}x^n = x^2 \sum_{n=2}^\infty a_{n-2}x^{n-2} = x^2g(x)$.

That means that $g(x) = 1 + x + x(g(x) - 1) + 2x^2g(x)$. From there you can solve for the generating function and work on extracting the coefficients.

Answer 2

Let $F(x)$ be $\sum_{n=0}^{\infty}a_nx^n$, the generating function.

To find the $F(x)$, rephrase the recurrence relation of the terms into an equation involving the generating function, like this: $$a_{n+2} = a_{n+1} + 2a_n$$ $$\sum_{n=0}^{\infty}a_{n+2}x^n = \sum_{n=0}^{\infty}a_{n+1}x^n + 2\sum_{n=0}^{\infty}a_nx^n$$ Now, since, for example, $\sum_{n=0}^{\infty}a_{n+1}x^n = \frac{F(x)-a_0}{x}$, we can write that as $$\frac{F(x)-a_0-a_1x}{x^2} = \frac{F(x)-a_0}{x} + 2F(x),$$ which, after a bit of algebra, can be solved for $F(x)$.

To find the explicit formula, you can take the rational function you get for $F(x)$, and expand it into a power series using partial fractions. The resulting formula may be quite messy, and involve roots of polynomials in the generating function.