Skip to main content

Section 2.1 Recurrence Relations

If we let \(a_n\) denote the number of ternary strings with no 012 substring, then \(a_0=1\text{,}\) \(a_1=3\text{,}\) \(a_2=9\) and

\begin{gather*} a_n = 3a_{n-1} - a_{n-3} \end{gather*}

so the characteristic equation is

\begin{gather*} x^3-3x^2+1=0 \end{gather*}

A plot of this cubic suggests three distinct real roots. Sage can find them approximately with numerical methods, or exactly. We are going to work exactly for as long possible and only resort to numerical approximations at the last possible moment.

First, we determine the roots. They might initially appear a bit complicated and involve long expressions with complex numbers. But explicitly request that they be simplified, but it also turns out that delaying this for as long as possible in subsequent computations is a good strategy. The result of the solve() function is a list of equations, with == as the equality. The .rhs() method will isolate the Right Hand Side of the equation.

Here are the approximate values of these three roots.

So our sequence is a linear combination of powers of these three roots. We can use the three initial values to create a system of three linear equations whose unknowns are the three coefficients. We build the coefficient matrix, solve for these coefficients, and request simplification. Note that we are using the un-simplified versions of the roots, the output above was just for show.

With the coeffiicents and the roots we can build the solution to the recurrence relation and test it.

login