Solving the linear recurrence $ f(n) = f(n - 1) + 12f(n-2)$

230 Views Asked by At

Solve the linear recurrence: $$ f(1) = 10, f(2) = -2,\quad f(n) = f(n - 1) + 12f(n-2)$$

My solution is below.

Assume:
$f(n) = x^n$

$$x^n = x^{n-1} + 12x^{n-2}$$
$$x^2 = x + 12 $$
$$x^2 - x - 12 = 0$$

Using the quadratic formula:

$$x_1 = 4 ,\quad x_2 = -3$$

Solution form:

c -> Unknown constant $$f(n) = c_1(4)^n + c2(-3)^n$$

$$10 = c_1 + c_2$$
$$-2 = 4(c_1) - 3(c2)$$

$$c_1 = 4, c_2 = 6$$

Closed form:

$$f(n) = 4(4)^n + 6(-3)^n$$

I'm not sure if did this correctly, but I'm having trouble with the last part with proving both the recurrence and closed form.

1

There are 1 best solutions below

0
On

There was a minor slip in finding the constants $c_1$ and $c_2$. The initial conditions are $f(1)=10$ and $f(2)=-2$, so the linear equations we get are $4c_1-3c_2=10$, $16c_1+9c_2=-2$. Solving, we get $c_1=1$ and $c_2=-2$.

Remark: You have found a closed form. Unless you are specifically asked, there is no need to prove that the closed form is correct. But if you wish to do so, it is easy to check by plugging in that $4^n -2(-3)^n$ is what it ought to be at $n=1$ and $n=2$. And we can verify by substitution that if $a_n=4^n-2(-3)^n$ then $a_n=a_{n-1}+12a_{n-2}$. The functions $f(n)$ and $a_n$ satisfy the same initial conditions, and the same recurrence, so (in principle by induction) they are equal at all positive integers.