0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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