I've been learning Linear Recurrences in my Discrete Math course and I've learned how to solve them when the characteristic equation is a quadratic. Is solving a linear recurrence with a cubic equation similar? This is the question I'm working on:
Solve the Linear Recurrence:
$f(0) = 0$
$f(1) = 0$
$f(2) = 18$
$f(n) = 3f(n − 1) − 4f(n − 3)$
…assuming the form will be of the kind $x^n$, I ended up getting:
$x^n = 3x^n-1 – 4x^n-3$
Which becomes the below once you divide the common factor from each term:
$x^3 = 3x^2 + 4$
Which is the cubic equation $x^2 – 3x^2 + 4$
Factoring everything out gave me the following Zeros: $2, 2, -1$ (not sure if this accurate, I'm using to factoring quadratics or using the quadratic equations to get zeros).
I then tried to set up a system of equations, but I've never done this $3$ equations:
$f(n) = a(2)^n + b(2)^n + c(-1)^n$
$f(0) = a(2)^0 + b(2)^0 + c(-1)^0 = a + b + c = 0$
$f(1) = a(2)^1 + b(2)^1 + c(-1)^1 = 2a + 2b – c = 0$
$f(2) = a(2)^2 + b(2)^2 + c(-1)^2 = 4a + 4b – c = 18$
…I have no idea if I did this correctly. I basically followed the procedure I used to solve a quadratic linear recurrence but now I'm stumped. Any help would be most welcome!
Best Answer
I'm not quite sure why you assumed it would be in the form of $x^n$. This looks like a linear recurrence that can be solved using matrices to me. This is how we get a new term: $$\left[\begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ -4 & 0 & 3\end{matrix}\right]\left[\begin{matrix} 0 \\ 0 \\ 18\end{matrix}\right]=\left[\begin{matrix}0 \\ 18 \\ 54\end{matrix}\right]$$ That last term is $f(3)$, which we get by applying this matrix once. Thus, if we apply this matrix $n$ times, we'll get $f(n+2)$, so we have: $$\left[\begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ -4 & 0 & 3\end{matrix}\right]^n\left[\begin{matrix} 0 \\ 0 \\ 18\end{matrix}\right]=\left[\begin{matrix}f(n) \\ f(n+1) \\ f(n+2)\end{matrix}\right]$$ Now, we can find the Jordan normal form of this matrix because it is not diagonalizable: $$\left[\begin{matrix}1 & 1 & -1 \\ -1 & 2 & -1 \\ 1 & 4 & 0\end{matrix}\right]\left[\begin{matrix}-1 & 0 & 0 \\ 0 & 2 & 1 \\ 0 & 0 & 2\end{matrix}\right]^n\left[\begin{matrix}\frac 4 9 & -\frac 4 9 & \frac 1 9 \\ -\frac 1 9 & \frac 1 9 & \frac 2 9 \\ -\frac 2 3 & -\frac 1 3 & \frac 1 3\end{matrix}\right]\left[\begin{matrix} 0 \\ 0 \\ 18\end{matrix}\right]=\left[\begin{matrix}f(n) \\ f(n+1) \\ f(n+2)\end{matrix}\right]$$ Now, we can use this formula to find the power: $$\left[\begin{matrix}1 & 1 & -1 \\ -1 & 2 & -1 \\ 1 & 4 & 0\end{matrix}\right]\left[\begin{matrix}(-1)^n & 0 & 0 \\ 0 & 2^n & n\cdot 2^{n-1} \\ 0 & 0 & 2^n\end{matrix}\right]\left[\begin{matrix}\frac 4 9 & -\frac 4 9 & \frac 1 9 \\ -\frac 1 9 & \frac 1 9 & \frac 2 9 \\ -\frac 2 3 & -\frac 1 3 & \frac 1 3\end{matrix}\right]\left[\begin{matrix} 0 \\ 0 \\ 18\end{matrix}\right]=\left[\begin{matrix}f(n) \\ f(n+1) \\ f(n+2)\end{matrix}\right]$$ Multiply everything together and take the first element to get your formula: $$f(n)=18\left(\frac{(-1)^n}{9}+\frac{2^{n+1}}{9}+\frac 1 3(n2^{n-1}-2^n)\right)$$ Simplify: $$f(n)=2(-1)^n-2^{n+1}+3n2^n$$