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

  • 7
    $\begingroup$ Well, that is elegant! (+1) $\endgroup$ – mrtaurho Jul 14 '19 at 15:35
  • 2
    $\begingroup$ You should really explain how you just "note" that first step... $\endgroup$ – user541686 Jul 15 '19 at 3:06
  • $\begingroup$ @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$. $\endgroup$ – Jam Jul 15 '19 at 12:27
  • $\begingroup$ @Jam I gave an explanation down. $\endgroup$ – Aqua Jul 15 '19 at 12:28
  • 1
    $\begingroup$ @Jam: I don't mean 'how' as in the mechanics of it... I mean 'how' as in, like, the inspiration. It's... not obvious. $\endgroup$ – 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}$.


Added at request of Mehrdad.

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

  • $\begingroup$ Haha thanks for adding this! I'd have just added it to your previous answer though :P people might get confused on that one without realizing this one clarifies it... $\endgroup$ – user541686 Jul 15 '19 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.