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
    Have you done any experiments at all with the first one? What happens is pretty clear. Also quite easy to prove.2012-12-16
  • 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