2

I apologize if this question is far too obvious, but I'm a bit confused (and new to this subject). I have to solve the recurrence relation:

$a_n=6a_{n-1}-9a_{n-2}$
$n=2,3,..$

Using Euler substitution, I get

$x^2-6x-9=0$

Solving this equation gives me $x_1=x_2=3$

The solution seemed to be obvious (since there weren't any initial conditions, I cannot determine $\lambda$ coefficients): $a_n=\lambda_1*3^n$

But the official one from my book is: $a_n=\lambda_1*3^n+\lambda_2*n*3^n$

The only explanation I'm left with is "Along with $3^n$, it's obvious that $n*3^n$ is another solution as well, which gives us $a_n=\lambda_1*3^n+\lambda_2*n*3^n$.

If anyone understands how they got the second solution, I would really appreciate an explanation. I assume it's something really obvious, but I can't see it. If the question isn't clear, please point me to it since I'm not sure I've translated it properly.

frostpad
  • 235

1 Answers1

1

But the official one from my book is: $a_n=\lambda_1 \cdot 3^n+\lambda_2 \cdot n \cdot 3^n$

That is indeed the general solution in the case of a root with multiplicity $2$, as is the case here since the characteristic polynomial is $(x-3)^2$.

You can verify that it works by direct substitution in the recurrence relation.

Or, for another way to derive it, divide both sides of the recurrence relation by $3^n$:

$$ \frac{a_n}{3^n} = 2 \cdot \frac{a_{n-1}}{3^{n-1}} - \frac{a_{n-2}}{3^{n-2}} $$

With $b_n = \dfrac{a_n}{3^n}$ the above can be written as $b_n=2 b_{n-1}-b_{n-2} \iff b_n-b_{n-1}=b_{n-1}-b_{n-2}$, in other words $b_n$ is an arithmetic progression, so $b_n = \lambda_1 + \lambda_2 \cdot n$ for some $\lambda_{1,2}$.

For the general case of roots with multiplicity $\gt 2$ see for example this or that.

dxiv
  • 76,497