Recursion $f(n) = 3f(n-1) - 4f(n-3)$ with $f(0) = 1$ , $f(1) = -3$ , $f(2) = 2$

Question

How can one solve the recursion

$$f(n) = 3f(n-1) - 4f(n-3)$$

The start values are

$f(0) = 1$

$f(1) = -3$

$f(2) = 2$

I tried to find a general pattern to prove it with induction, but I can't find one...

Answer 1

Consider the general method. For $$f(n) = 3f(n-1) - 4f(n-3)$$ the characteristic equation is $$r^3=3r^2-4$$ $r=-1$ is an obvious root. Now use division to get the quadratic and then the two other roots.

Answer 2

We can also use generating functions: $$g(x):=\sum_{n \in \mathbb{N}}f(n)x^n$$ So we have that $$g(x)=f(0)x^0+f(1)x^1+f(2)x^2+\sum_{n \geq 3}f(n)x^n$$ $$=1-3x+2x^2+\sum_{n \geq 3}f(n)x^n$$ $$=1-3x+2x^2+\sum_{n \geq 3}(3f(n-1)-4f(n-3))x^n$$ $$=1-3x+2x^2+3\sum_{n \geq 3}f(n-1)x^n-4\sum_{n \geq 3}f(n-3)x^n$$ $$=1-3x+2x^2+3\sum_{n \geq 3}f(n-1)x^{n-1}x-4\sum_{n \geq 3}f(n-3)x^{n-3}x^3$$ $$=1-3x+2x^2+3x\sum_{n \geq 3}f(n-1)x^{n-1}-4x^3\sum_{n \geq 3}f(n-3)x^{n-3}$$ $$=1-3x+2x^2+3x\sum_{n \geq 2}f(n)x^{n}-4x^3\sum_{n \in \mathbb{N}}f(n)x^{n}$$ $$=1-3x+2x^2+3x\left(\sum_{n \geq 2}f(n)x^{n}+f(0)x^0+f(1)x^1-f(0)x^0-f(1)x^1\right)-4x^3\sum_{n \in \mathbb{N}}f(n)x^{n}$$ $$=1-3x+2x^2+3x\left(\sum_{n \in \mathbb{N}}f(n)x^{n}-f(0)x^0-f(1)x^1\right)-4x^3\sum_{n \in \mathbb{N}}f(n)x^{n}$$ $$=1-3x+2x^2+3x\left(g(x)-1+3x\right)-4x^3g(x)$$ So: $$g(x)=1-3x+2x^2+3x\left(g(x)-1+3x\right)-4x^3g(x)$$ $$g(x)=1-3x+2x^2-3x+9x^2+3xg(x)-4x^3g(x)$$ $$g(x)(1-3x+4x^3)=1-6x+11x^2$$ $$g(x)=\frac{1-6x+11x^2}{1-3x+4x^3}$$ Doing partial fraction decomposition on $g$ (I'll leave it for you): $$g(x)=\frac{2}{x+1}+\frac{1/2}{(2x-1)^2}+\frac{3/2}{2x-1}$$ And now we can use taylor series: $$g(x)=2\left(\sum_{n \in \mathbb{N}}{(-1)^nx^n}\right)+\frac{1}{2}\left(\sum_{n \in \mathbb{N}}2^nx^n(1+n)\right)-\frac{3}{2}\left(\sum_{n \in \mathbb{N}}2^nx^n\right)$$ $$g(x)=\sum_{n \in \mathbb{N}}x^n\left(2(-1)^n+\frac{1+n}{2}2^n-\frac{3}{2}2^n\right)$$ $$g(x)=\sum_{n \in \mathbb{N}}x^n\left(2(-1)^n+(n-2)2^{n-1}\right)$$ But the coefficient of $x^n$ in $g(x)$ is $f(n)$: $$f(n)=2(-1)^n+(n-2)2^{n-1}$$ And if you worry about the validity of the manipulations, you can check the result with induction, for example.

Answer 3

Suppose that $f(n)=a^n$.

This gives the following equation:

$$a^n-3a^{n-1}+4a^{n-3}=0$$

$$a^{n-3}(a^3-3a^2+4)=0$$

$$a^3-3a^2+4=0\tag{1}$$

One solution is obviously $a=-1$. Equation (1) can be now factorized in the following way:

$$(a+1)(a^2-4a+4)=0$$ $$(a+1)(a-2)^2=0$$

So we have three roots with two of them being equal:

$$a_1=-1,a_2=a_3=2$$

It can be shown that the general solution $f(n)$ is a sum of partial solutions of the form $C_ia_i^n$ if the multiplicity of the solution is 1. If you have a solution with multiplicity 2, the partial solution has the form $(C_i+C_{i+1}n)a_i^n$. In general if you have a solution with multiplicity k, the partial solution will be:

$$(C_i+C_{i+1}n+...+C_{i+k-1}n^{k-1})a_i^n$$

In our case, the solution is of the form:

$$f(n)=C_1(-1)^n+(C_2+C_3n)2^n$$

Constants $C_1$, $C_2$, $C_3$ can be obtained from initial conditions:

$$f(0)=C_1+C_2=1$$

$$f(1)=-C_1+2C_2+2C_3=-3$$

$$f(2)=C_1+4C_2+8C_3=2$$

The solutions are: $C_1=2$, $C_2=-1$ and $C_3={1 \over 2}$

So the final solution is:

$$f(n)=(-1)^n\times 2+(-1+\frac n2)\times 2^n$$

$$f(n)=(-1)^n\times 2+(n-2)\times 2^{n-1}$$

$$\boxed{f(n)=2\times[(-1)^n+(n-2)\times 2^{n-2}]}$$

To understand all the details you need to read some theory and a good starting point could be here.