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?
Best Answer
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$.