I am trying to find the general solution to a two-term linear recurrence $F(n) = aF(n-1) + bF(n-2)$ but not sure what I am doing.

$G(x) = \sum_{n=0}^{\infty}F(n)x^n$

$G(x) = F(0) + F(1)x + a\sum_{n=2}^{\infty}F(n-1)x^n + b\sum_{n=2}^{\infty}F(n-2)x^n$

$G(x) = F(0) + F(1)x + ax(-F(0) + \sum_{n=0}^{\infty}F(n)x^{n}) + bx^2\sum_{n=0}^{\infty}F(n)x^n$

$G(x) = F(0) + F(1)x + ax(-F(0) + G(x)) + bx^2G(x)$

$G(x)(1 - ax - bx^2) = F(0) - axF(0) + F(1)x$

$G(x) = \frac{F(0) - axF(0) + F(1)x}{1 - ax - bx^2}$

I can't tell if this is even right so far. I get the following for the roots of the denominator:

$r_1 = \frac{a + \sqrt{a^2+4b}}{-2b}, r_2 = \frac{a - \sqrt{a^2+4b}}{-2b}$

$G(x) = \frac{F(0) - axF(0) + F(1)x}{(x-r_1)(x-r_2)}$

Partial fractions:

$G(x) = \frac{p_1}{x-r_1} + \frac{p_2}{x-r_2}$

$p_1 \cdot(x-r_2) + p_2 \cdot(x-r_1) = F(0) - axF(0) + F(1)x$

and then

$p_2 \cdot(r_2-r_1) = F(0) - ar_2F(0) + F(1)r_2 \implies p_2 = \frac{F(1)r_2}{r_2-r_1}$

$p_1 \cdot(r_1-r_2) = F(0) - ar_1F(0) + F(1)r_1 \implies p_1 = \frac{F(1)r_1}{r_1-r_2}$

But none of this is simplifying nicely. I am ultimately expecting it to lead to something that looks kind of like $F(n) = \alpha r_1^n + \beta r_2^n$ (although I think it's also possible for one of the terms to look like $\alpha n r_1^n$ as well, but I digress).

Where am I going wrong?


1 Answer 1


If we assume there is a solution of the form $F(n)=r^n$, then we get $r^n=ar^{n-1}+br^{n-2}$, or $r^2-ar-b=0$. Thus, we obtain $r_{1,2}=\dfrac{a\pm\sqrt{a^2-4b}}{2}$. If these are distinct, then the general solution of of the form $F(n)=\alpha r_1^n+\beta r_2^n$. If these are not distinct, you can show that $nr^n$ also satisfies this linear equation. Thus, the general solution is of the form $F(n)=\alpha r^n+\beta nr^n$.

Now, as for why two distinct solutions is sufficient, notice that the solution space is a 2-dimensional vector space (consider the solutions with $F(0)=1$ and $F(1)=0$ and solutions with $F(0)=0$ and $F(1)=1$ - you can obtain the solution for any initial conditions in this way). Further, in both cases the solutions provided above are linearly independent.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .