2

The method I found for solving recursive equations starts like this:

First, I express the equation with the help of polynomials $q$, so

$$q^n = 6q^{n-1} - 9q^{n-2}.$$

This is equivalent to

$$q^2 = 6q - 9,$$

which can be solved with the $p-q$-formula.

The goal is to solve this system of linear equations:

$$f(0) = a_1 + a_2 = 0$$ $$f(1) = a_1q_1 + a_2q_2 = 1$$

with $q_1$ and $q_2$ being the solutions that I receive with the help of the $p-q$-formula. But: The $p-q$-formula only yields one solution in this case, which is $q_1 = 3$, and hence, I don't know how to go further from here.

Julian
  • 1,401
  • 4
    When we have a second order homogeneous linear recurrence relation with repeated roots, the general solution is given by: $$f(n)=c_1 \lambda^n+c_2 n\lambda^n$$ Where $\lambda$ is the root of the quadratic characteristic equation. For an $n$-th order linear homogeneous recurrence, see here. – projectilemotion Aug 30 '17 at 09:51

2 Answers2

4

HINT:

As $q^2-6q+9=(q-3)^2,$

$$f(n)=(an+b)3^n$$ where $a,b$ are arbitrary constants to be determined from the initial conditions

lab bhattacharjee
  • 274,582
0

It's just $f(n)=n3^{n-1}$, but I like the following way: $$f(n)-3f(n-1)=3(f(n-1)-3(f(n-2)),$$ which gives $$f(n)-3f(n-1)=3^{n-1}$$ and from here we obtain: $$f(n)-3f(n-1)=3^{n-1}$$ $$3f(n-1)-9f(n-2)=3^{n-1}$$ $$.$$ $$.$$ $$.$$ $$3^{n-1}f(1)-3^nf(0)=3^{n-1},$$ which after summing gives $$f(n)-3^nf(0)=n3^{n-1}$$ or $$f(n)=n3^{n-1}.$$

Michael Rozenberg
  • 194,933