0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.