Linear recurrence problem

Question

Solve linear recurrence

f(1) = 12, f(2) = 16,

f(n) = 4f(n − 2).

Hint: the solution has integer coefficients, so if you get square roots and/or difficult fractions, it’s likely that you have made a mistake somewhere.

So far i got:

f(n) = x²

f(n) = 4f(n - 2)
  x² = 4x^(n-2)
     = 4x^(2-2)
     = 4

Usually I get an quadratic equation or something with the multiplicity of 2, but I got a single integer, how do I solve this?

This is also a quadratic equation. $x^2-4=0$ has 2 roots, $+2$ and $-2$. — Aritra Das, Oct 05 '15 at 15:43

score 2 · Accepted Answer · answered Oct 05 '15 at 15:32

2

Outline

Assume $r^n$ is a solution, then the given condition reduces the equation to $r^n = 4r^{n-2}$ which means $r^2 = 4$, or $r = \pm 2$. This is where you are kind of stuck.

Now the general solution is given by $f(n) = a2^n + b(-2)^n$.

Given $f(1) = 12$ and $f(2) = 16$, you will get $a = 5$ and $b = -1$ so the most general solution is given by

$\color{blue}{f(n) = 5\times2^n - (-2)^n}$

answered Oct 05 '15 at 15:32

Shailesh

3,789

@milkbread. Thank you. Glad I could be of help. You had kind of shown efforts, so I had no problem in clarifying doubts – Shailesh Oct 05 '15 at 16:44

Linear recurrence problem

1 Answers1