Bsrgvty

Suppose $f(1)=1$ and $f(2)=7$. For $nge 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 $$boxeda_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 $$boxeda_n+1-3a_n = 4^n$$

• Step 3

If you substract those formulas in boxes you get:

$$boxeda_n = 4^n- 3^n$$

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)=acdot 3^n+bcdot 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:

beginalign*
overbracebeginbmatrix a_n+1 \ a_nphantom+1 endbmatrix^x_n+1
&= overbracebeginbmatrix 7 & -12 \ 1 & 0 endbmatrix^A
overbracebeginbmatrix a_nphantom-1 \ a_n-1 endbmatrix^x_n \
&= beginbmatrix 7 & -12 \ 1 & 0 endbmatrix^n-1
beginbmatrix 7 \ 1 endbmatrix
endalign*

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

beginalign*
A^n = beginbmatrix 4 & 1 \ 3 & 1 endbmatrix^-1beginbmatrix 4^n & 0 \ 0 & 3^n endbmatrix beginbmatrix 4 & 1 \ 3 & 1 endbmatrix
endalign*

which you can substitute to obtain $a_n+1$.

Added at request of Mehrdad.

Say we have $$boxeda_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 $boxedb_n =a_n-xa_n-1$ and $boxedc_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...