# 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$)?

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?

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}$$

• Well, that is elegant! (+1) – mrtaurho Jul 14 '19 at 15:35
• You should really explain how you just "note" that first step... – user541686 Jul 15 '19 at 3:06
• @Mehrdad it's a simple algebraic rearrangement using $a_{n+1}=f(n)$ to get $f(n)=7f(n-1)-12f(n-2)\Rightarrow a_{n+1}=7a_n-12a_{n-1}\Rightarrow \ldots$. – Jam Jul 15 '19 at 12:27
• @Jam I gave an explanation down. – Aqua Jul 15 '19 at 12:28
• @Jam: I don't mean 'how' as in the mechanics of it... I mean 'how' as in, like, the inspiration. It's... not obvious. – user541686 Jul 15 '19 at 17:35

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$$.

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}$$.

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...