1
$\begingroup$

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?

  • 0
    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.2012-12-16

5 Answers 5

1

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.

  • 0
    $50$ percent of the cases in the original question are eventually periodic, so OP might take issue with your evaluation of practicality.2013-01-23
0

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}$.

0

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.

0

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

  • 0
    Even generating functions $p$ose problems in degrees three and up.2013-01-23
0

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.

  • 0
    @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.2013-01-23