What is the closed form of the $f$ with $f(1)=1$, $f(2)=7$ and $f(n)=7f(n-1)-12f(n-2)$ ($n\ge 3$)?

Question

Suppose $f(1)=1$ and $f(2)=7$. For $n\ge 3$ we have $$f(n)=7f(n-1)-12f(n-2). $$ What is the closed form of the function $f$?

---

I've tried unrolling it but it gets very complicated very quickly without a clear pattern emerging. Any ideas?

Answer 1

Write $a_n = f(n)$ instead.

Step 1

You can note that $$a_{n+1}-4a_n = 3(a_n-4a_{n-1})$$ so putting $b_n=a_n-4a_{n-1}$ you get $$b_{n+1} = 3b_n$$ so $b_n$ is geometric progression, with $b_2=3$ so $b_1=1$ and thus $$b_n = 3^{n-1}$$ so $$\boxed{a_{n+1}-4a_n =3^n}$$

Step 2

You can also note that $$a_{n+1}-3a_n = 4(a_n-3a_{n-1})$$ so putting $c_n=a_n-3a_{n-1}$ you get $$c_{n+1} = 4c_n$$ so $c_n$ is geometric progression, with $c_2=4$ so $c_1=1$ and thus $$c_n = 4^{n-1}$$ so $$\boxed{a_{n+1}-3a_n = 4^{n}}$$

Step 3

If you substract those formulas in boxes you get:

$$\boxed{a_n = 4^{n}- 3^n}$$

Answer 2

The characteristic equation is $x^2-7x+12=0$, which factors as $(x-3)(x-4)=0$, yielding two roots, 3 and 4. So $f(n)=a\cdot 3^n+b\cdot 4^n$ for some constants $a$ and $b$. Now use the values of $f(1)$ and $f(2)$ to solve for $a$ and $b$.

Answer 3

Unfortunately I don't know what your mathematical background is to know if this is a useful answer, but I'll post it for the sake of completeness.

What you have is a linear constant-coefficient difference equation.

There are lots of ways to solve them, some specialized, but the usual generic one is linear algebra:

\begin{align*} \overbrace{\begin{bmatrix} a_{n+1} \\ a_{n\phantom{+1}} \end{bmatrix}}^{x_{n+1}} &= \overbrace{\begin{bmatrix} 7 & -12 \\ 1 & 0 \end{bmatrix}}^A \overbrace{\begin{bmatrix} a_{n\phantom{-1}} \\ a_{n-1} \end{bmatrix}}^{x_n} \\ &= \begin{bmatrix} 7 & -12 \\ 1 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} 7 \\ 1 \end{bmatrix} \end{align*}

Now you want to compute $A^{n-1}$, for which you'd diagonalize $A$ and get

\begin{align*} A^n = \begin{bmatrix} 4 & 1 \\ 3 & 1 \end{bmatrix}^{-1}\begin{bmatrix} 4^n & 0 \\ 0 & 3^n \end{bmatrix} \begin{bmatrix} 4 & 1 \\ 3 & 1 \end{bmatrix} \end{align*}

which you can substitute to obtain $a_{n+1}$.

Answer 4

Say we have $$\boxed{a_{n+1} = (x+y)a_n-xya_{n-1}}$$ then we can do: $$a_{n+1}-xa_n = y(a_n-xa_{n-1})$$ and $$a_{n+1}-ya_n = x(a_n-ya_{n-1})$$

Putting $\boxed{b_n =a_n-xa_{n-1}}$ and $\boxed{c_n = a_n-ya_{n-1}}$ we can finish as before.

In general $x,y$ are solution of quadratic (characteristic) equation $t^2-pt-q=0$ of recursion $$a_{n+1} = pa_n+qa_{n-1}$$

---

One more example: $$a_{n+1} = 2a_n+8a_{n-1}.$$ Then we can do $$a_{n+1}+2a_n = 4(a_n+2a_{n-1})$$ and $$a_{n+1}-4a_n = -2(a_n-4a_{n-1})$$

Then with $b_n =a_n+2a_{n-1}$ and $c_n = a_n-4a_{n-1}$ we are done...