Matthew wrote:

> \$x\_{n} = x\_{n-1} + x\_{n-2} + x\_{n-3} \$

Cool, the Tribonacci numbers! I discussed them in Week 1 of this course, and gave some homework about them - you can see solutions:

* [Quantization and Categorification](http://math.ucr.edu/home/baez/qg-winter2004/), Winter 2004.

This could lead you down an even deeper rabbit-hole than the one you're exploring now!

> How would you make a matrix to represent this recurrence?

This is going to take some work, so I will only give you the answer because you flattered me so much. (They say "flattery gets you nowhere," but they're lying.)

There's a famous way to convert higher-order linear ordinary differential equations into systems of first-order ones. For example if we take

$\frac{d^2}{d t^2} x(t) = 3 \frac{d}{dt} x(t) + 7 x(t)$

and write \$$\dot{x}\$$ for \$$\frac{d}{dt} x(t)\$$ it becomes

$\frac{d}{dt} \left(\begin{array}{c} \dot{x} \\\\ x \end{array}\right) = \left(\begin{array}{cc} 3 & 7 \\\\ 1 & 0 \end{array} \right) \left(\begin{array}{c} \dot{x} \\\\ x \end{array}\right) .$

We can then solve the equation using matrix tricks. More to the point, a similar trick works for linear recurrences. So we can take

$x\_{n+2} = 3 x\_{n+1} + 7 x\_n$

and write it as

$\left(\begin{array}{c} x\_{n+2} \\\\ x\_{n+1}\end{array}\right) = \left(\begin{array}{cc} 3 & 7 \\\\ 1 & 0 \end{array} \right) \left(\begin{array}{c} x\_{n+1} \\\\ x\_n \end{array}\right) .$

We can make it even more slick using an "evolution operator" \$$U\$$ that increments the "time" \$$n\$$ by one step. By definition

$U \left(\begin{array}{c} x\_{n+1} \\\\ x\_{n}\end{array}\right) =\left(\begin{array}{c} x\_{n+2} \\\\ x\_{n+1}\end{array}\right) .$

Then our earlier equation becomes

$U \left(\begin{array}{c} x\_{n+1} \\\\ x\_{n}\end{array}\right) = \left(\begin{array}{cc} 3 & 7 \\\\ 1 & 0 \end{array} \right) \left(\begin{array}{c} x\_{n+1} \\\\ x\_n \end{array}\right) .$

but this just means

$U = \left(\begin{array}{cc} 3 & 7 \\\\ 1 & 0 \end{array} \right)$

so we know stuff like

$\left(\begin{array}{c} x\_{n+23} \\\\ x\_{n+22}\end{array}\right) = U^{23} \left(\begin{array}{c} x\_{n+1} \\\\ x\_n \end{array}\right)$

I think the answer to your question is lurking in what I said. Note that I considered a second-order differential equation and a second-order recurrence, but the exact same idea works for the third-order one you are interested in. You just need a \$$3 \times 3\$$ matrix instead of a \$$2 \times 2\$$.