Solve the recurrence relation $f(n) = f(n - 1) + f(n - 2) + f(n - 3)$

Question

This is a problem I was playing with that troubled me greatly.

$f(n) = f(n - 1) + f(n - 2) + f(n - 3)$

$f(1) = f(2) = 1$

$f(3) = 2$

So, the goal is to try and find a solution for f(n).

I tried using the regular method that is given in Johnsonbaugh , which involves finding a solution to an alternative recurrence relation, given by:

$S_{n} = t^{n}$

$S_{n} = S_{n - 1} + S_{n - 2} + S_{n-3}$

$t^{n} = t^{n - 1} + t^{n - 2} + t^{n - 3}$

$t^{n} - t^{n - 1} - t^{n - 2} - t^{n - 3} = 0$

$t^{3} - t^{2} - t - 1 = 0$

Now, you're supposed to find the roots of the above auxiliary equation, but you need all of the roots, and two of them are complex

$t = 1.8393$,

and also:

$t = -0.41964 + 0.60629i$

and its conjugate

$t = -0.41964 - 0.60629i$

Therefore,

$S_{n} = a(1.8393)^{n} + b(-0.41964 + 0.60629i)^{n} + c(-0.41964 - 0.60629i)^{n}$

Now, it is a matter of solving the set of linear equations for $a$, $b$, $c$ given by the initial conditions.

$S_{1} = 1 = a(1.8393) + b(-0.41964 + 0.60629i) + c(-0.41964 - 0.60629i)$ $S_{2} = 1 = a(1.8393)^{2} + b(-0.41964 + 0.60629i)^{2} + c(-0.41964 - 0.60629i)^{2}$ $S_{3} = 2 = a(1.8393)^{3} + b(-0.41964 + 0.60629i)^{3} + c(-0.41964 - 0.60629i)^{3}$

Now, this is supposed to yield a solution for f(n), if I didn't mess anything up, where

$f(n) = a(1.8393)^{n} + b(-0.41964 + 0.60629i)^{n} + c(-0.41964 - 0.60629i)^{n}$

Now, how do I solve this, and is it right?

Answer 1

It's totally fine to have complex roots, because they will come in conjugate pairs, so when you raise each to the same power and add, the imaginary parts will cancel. I didn't check all your math in great detail but your overall approach looks fine. The only minor thing I would suggest is that if you want your answer to be totally correct, you should write down the roots in closed form instead of with decimal approximations. As for how to solve for $a,b,c$, you have the equations and so you just need to solve a $3 \times 3$ linear system of equations. If you don't know how to solve a linear system, you can look it up online, it's pretty easy.

Answer 2

In matrix form, we can construct a matrix $A=\left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right)$ such that

$\left( \begin{array}{c} f(n+1) \\ f(n) \\ f(n-1) \end{array} \right) = \left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right) % \left( \begin{array}{c} f(n) \\ f(n-1) \\ f(n-2) \end{array} \right) = A \left( \begin{array}{c} f(n) \\ f(n-1) \\ f(n-2) \end{array} \right)$

Generalizing, we shall have,

$\left( \begin{array}{c} f(n+k) \\ f(n+k-1) \\ f(n+k-2) \end{array} \right) = A^k \left( \begin{array}{c} f(n) \\ f(n-1) \\ f(n-2) \end{array} \right)$

Let's put $k=n−3$ and $n=3$, then we shall have

$\left( \begin{array}{c} f(n) \\ f(n-1) \\ f(n-2) \end{array} \right) = A^{n-3} \left( \begin{array}{c} f(3) \\ f(2) \\ f(1) \end{array} \right)$

With spectral decomposition of $A=V\Lambda V^{-1}$, where we have

$\Lambda=\left( \begin{array}{ccc} 1.8392868 & 0 & 0 \\ 0 & -0.4196434+0.6062907i & 0 \\ 0 & 0 & -0.4196434-0.6062907i \end{array} \right)=\left( \begin{array}{ccc} 1.8392868 & 0 & 0 \\ 0 & (0.7373527)e^{(2.176234)i} & 0 \\ 0 & 0 & (0.7373527)e^{-(2.176234)i} \end{array} \right)$

and

$V = \left( \begin{array}{ccc} -0.8503402 & -0.1411941-0.3752032i & -0.1411941+0.3752032i \\ -0.4623206 & -0.3094252+0.4470501i & -0.3094252-0.4470501i \\ -0.2513586 & 0.7373527 & 0.7373527 \end{array} \right)$

so that

$\Lambda^n=\left( \begin{array}{ccc} 1.8392868^n & 0 & 0 \\ 0 & (0.7373527)e^{(2.176234)ni} & 0 \\ 0 & 0 & (0.7373527)e^{-(2.176234)ni} \end{array} \right)$

Hence, we have

$\left( \begin{array}{c} f(n) \\ f(n-1) \\ f(n-2) \end{array} \right) = V\Lambda^{n-3}V^{-1} \left( \begin{array}{c} f(3) \\ f(2) \\ f(1) \end{array} \right) = V\Lambda^{n-3}V^{-1} \left( \begin{array}{c} 2 \\ 1 \\ 1 \end{array} \right)$

For example, for $n=20$, we have,

$\left( \begin{array}{c} f(20) \\ f(19) \\ f(18) \end{array} \right) = V\Lambda^{17}V^{-1} \left( \begin{array}{c} 2 \\ 1 \\ 1 \end{array} \right) =\left( \begin{array}{c} 66012 \\ 35890 \\ 19513 \end{array} \right)$