Recurrence relation - equal roots of characteristic equation

Question

I have the following problem:

Solve the following recurrence relation

$f(0)=3$

$f(1)=12 $

$f(n)=6f(n-1)-9f(n-2)$

We know this is a homogeneous 2nd order relation so we write the characteristic equation: $a^2-6a+9=0$ and the solutions are $a_{1,2}=3$.

The problem is when I replace these values I get:

$$f(n)=c_13^n+c_23^n$$

and using the 2 initial relations I have:

$$f(0)=c_1+c_2=3$$ $$f(1)=3(c_1+c_2)=12$$

which gives me that there are no values such that $c_1$ and $c_2$ such that these 2 relation are true.

Am I doing something wrong? Is the way it should be solved different when it comes to identical roots for the characteristic equation?

Answer 1

Let the roots of the characteristic equation be $\alpha, \beta$ so the equation is $$f(n)=(\alpha+\beta)f(n-1)-\alpha\beta f(n-2)$$ with solution $f(n)=A\alpha^n+B\beta^n$

We set $f(0)=3, f(1)=12$ to obtain $A+B=3$ and $A\alpha+B\beta=12$ with $B=\frac {3\alpha-12}{\alpha-\beta}$ and $A=\frac {12-3\beta}{\alpha-\beta}$ so $$f(n)=12\frac {\alpha^n-\beta^n}{\alpha-\beta}-3\alpha\beta\frac {\alpha^{n-1}-\beta^{n-1}}{\alpha-\beta}$$

Now you can divide through by $\alpha-\beta$ and get $n$ terms from the first fraction and $n-1$ terms from the second. In the limit when $\alpha$ becomes equal to $\beta$ this leads to $$f(n)=12n\alpha^{n-1}-3(n-1)\alpha^n=3\alpha^n+\left(\frac {12}{\alpha}-3\right)n\alpha^n= \text {(in form) }(C+Dn)\alpha^n$$

This is one way of justifying the general form others have used - you get the solution you need by setting $\alpha=3$.

Answer 2

When characteristic polynomial has coincident roots the correct equation is the following: $$ f(n) = c_03^n + c_1 n\cdot 3^n $$

This phenomenon happens when you solve linear "things", like linear differential equations.

Answer 3

Yes, you’re doing something wrong. In the case of repeated roots, your approach collapses the two solutions into a single one, when in fact you need two independent solutions. If the characteristic equation has a root $r$ of multiplicity $m$, it gives rise to the $m$ solutions $c_1r^n,c_2nr^n, \ldots,c_mn^{m-1}r^n$. In your case $r=3$ and $m=2$, so you get $c_13^n$ and $c_2n3^n$. That is,

$$f(n)=c_13^n+c_2n3^n=(c_1+c_2n)3^n\;.$$

Now proceed as you would in the case of distinct roots to find $c_1$ and $c_2$ that match your initial conditions.