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\\).

> \\[ 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\\).