# Recurrence relation - equal roots of characteristic equation

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?

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.

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$.

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.