# How do we deal with recurrence relation characteristic equations that are not quadratic or have imaginary roots?

Suppose we have $$H(n) = H(n-1)-H(n-2) \rightarrow x^2-x+1 \rightarrow r_1 = \frac{1+\sqrt{-3}}{2}, r_2 = \frac{1-\sqrt{-3}}{2}$$

or

$$H(n) = H(n-1)+H(n-2)+H(n-3) \rightarrow x^3-x^2-x-1=0$$

In either case, how would the recurrence relation be solved? Are there other techniques for complex roots/non-quadratics?

-
Have you done any experiments at all with the first one? What happens is pretty clear. Also quite easy to prove. – Will Jagy Dec 16 '12 at 4:39
The second example is called the tribonacci numbers, whatever you take as your first three numbers. The real root is bigger than one, the complex roots are smaller than one in magnitude, so the power of the real root is what dominates, similar in style to Fibonacci/Lucas. – Will Jagy Dec 16 '12 at 4:47

If you apply the techiques applicable to quadratics/real roots with complex numbers, you'll see that at the end you have pairs of conjugate complex numbers that add up to reals. Just that the solutions aren't monotonic, they fluctuate.

Just take a look at what happens if you end up with $A(z) = \frac{1}{1 + z + z^2}$.

-

If the characteristic polynomial has distinct roots $r_1,r_2,\dots,r_m$ then the general solution of the recurrence is $H(n)=a_1r_1^n+a_2r_2^n+\cdots+a_mr_m^n$. Actually finding the roots $r_1,r_2,\dots,r_m$ may be difficult/impossible if $m\ge3$, but if you can find those roots the formula holds.

-

From my experience, there are two directions to approaching recursive equations. The first direction is from a pure-math perspective. If we approach from this angle, it is usually sufficient to compute the form of a solution, possibly in an abstract manner. In this case, once we have reduced to finding roots of polynomials, we are done - everything has been described.

The other direction is from a computer science or applied math perspective. Oftentimes, we want to make numerical statements about the growth rate of the sequence, to a fairly high degree of precision. From this perspective, things are even simpler. Once you have obtained the characteristic equation, simply approximate the root of largest magnitude. Then you can approximate the sequence by a geometric series in the largest root.

The situation is pretty concrete in either case, in my opinion. Decide which direction you are actually interested in, and then apply the corresponding techniques.

-
Approximating the sequence is a bit harder than what you've written, if there's a repeated root and/or a tie for root of largest magnitude. – Gerry Myerson Jan 23 '13 at 5:31
I wanted to outline the main ideas without getting caught up on technical details. You're correct that the picture is more interesting in the probability-$0$ "edge" cases. Such cases were discussed in a similar question here (math.stackexchange.com/questions/62383/…). My additional $2$-cents is that there is only one essentially "bad" case where asymptotics fail: if the sequence is eventually periodic. This is not a practical issue, as far as I am aware. – pre-kidney Jan 23 '13 at 17:52
$50$ percent of the cases in the original question are eventually periodic, so OP might take issue with your evaluation of practicality. – Gerry Myerson Jan 23 '13 at 23:47

There are some efficient techniques for tackling recurrence relations such as generating function technique and some transform techniques such as the Z-transform technique.

-
Even generating functions pose problems in degrees three and up. – Gerry Myerson Jan 23 '13 at 5:29

The first one repeats $$a,b,b-a,-a,-b,a-b, a,b,b-a,-a,-b,a-b, a,b,b-a,-a,-b,a-b, a,b,c,-a,-b,a-b,\ldots$$

This does follow, eventually, from the description $$H(n) = A \, r_1^n + B \, r_2^n$$ for some complex constants $A,B.$

Indeed, $$\left( \begin{array}{r} A \\ B \end{array} \right) = \left( \begin{array}{rr} \frac{1}{2} - \frac{i}{2 \sqrt 3} & -\frac{1}{2} - \frac{i}{2 \sqrt 3} \\ \frac{1}{2} + \frac{i}{2 \sqrt 3} & -\frac{1}{2} + \frac{i}{2 \sqrt 3} \end{array} \right) \cdot \left( \begin{array}{r} a \\ b \end{array} \right)$$

So, for the sequence $$1,-1,-2,-1,1,2, 1,-1,-2,-1,1,2,\ldots$$ we have $a=1,b=-1,$ then $A=1,B=1$ and $$H(n) = r_1^n + r_2^n.$$

For the sequence $$1,1,0,-1,-1,0, 1,1,0,-1,-1,0,\ldots$$ we have $a=1,b=1,$ then $A=- \frac{i}{ \sqrt 3} ,B= \frac{i}{ \sqrt 3}$ and $$H(n) = - \frac{i}{ \sqrt 3} \left( r_1^n - r_2^n \right).$$

The repetition of length 6 and the half-repetition with negation of length 3 can be seen from both roots satisfying $r_j^6 = 1$ and $r_j^3 = -1.$ Or, you can just start a sequence with symbols $a,b$ and confirm the pattern I gave first.

-
Absence of evidence is not evidence of absence. In any event, solving the recurrence may mean finding a formula for $H(n)$, in which case after you've seen it's $a,b,b-a,-a,-b,a-b$ repeating you still have to find a formula for it (which I know you can do, Will, but maybe not everyone can). – Gerry Myerson Jan 23 '13 at 5:35
@Gerry, hi. I had hoped, back in December, that the OP would at least try a few examples of the first one. There were several steps getting from the two roots to this...if there had been any feedback I might have filled in some of that. – Will Jagy Jan 23 '13 at 5:41
Curious that this question got so little attention when first posted, and is getting so much now, over a month later. My excuse: I was on an airplane most of 16 December. – Gerry Myerson Jan 23 '13 at 5:47
@Gerry, not entirely sure how that happened, except that you or vonbrand posted something two hours ago. The OP is long gone. I finally put something because of the new activity. – Will Jagy Jan 23 '13 at 5:54