14
$\begingroup$

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?

$\endgroup$
41
$\begingroup$

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

$\endgroup$
6
  • 7
    $\begingroup$ Well, that is elegant! (+1) $\endgroup$
    – mrtaurho
    Jul 14 '19 at 15:35
  • 3
    $\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
37
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
2
  • $\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
  • $\begingroup$ @user541686 I know this was an old post, but I gave an explanation using forward shift operator here: math.stackexchange.com/questions/3903217/… Also see math.stackexchange.com/questions/3906793/… for another example using forward shift operator. $\endgroup$
    – Neat Math
    Nov 16 '20 at 21:45

Your Answer

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