0

The Fibonacci sequence $x_n = x_{n-1} + x_{n-2}$ has growth rate $O(\phi^n)$. If we generalize this recurrence to $x_n = x_{n-1} + Cx_{n-2}$ where $C \in [0, \infty)$, what can we say about its growth rate?

Line
  • 11
  • 3
    It depends on the sizes of the roots of $x^2=x+C$. – lhf Aug 10 '21 at 21:32
  • 2
    It also depends on the initial conditions. If $x_{n} = x_{n-1} + 2 x_{n-2}$ then it could happen that $x_0 = 1$ and $x_1 = 2$ and then $x_n = 2^n$ but it could also happen that $x_0 = 1$ and $x_{1} = -1$ and then $x_n = (-1)^n$. To be fair, for a fixed $x_0$, you get the growth rate from the larger root for every parameter of $x_1$ except for one exception, that exception being when $x_1$ is $x_0$ times the other root. – user952367 Aug 10 '21 at 22:01

1 Answers1

5

You can solve the following equation first:

$$ x^2 - x - C = 0 $$

Solutions are $\frac{1 \pm \sqrt{1+4C}}{2}$. Hence, as $C > 0$, the growth of the recurrent equation is $\left ( \frac{1 + \sqrt{1+4C}}{2} \right )^n$. In particular, for $C=1$, you will get the Fibonacci solution.

HallaSurvivor
  • 38,115
  • 4
  • 46
  • 87
OmG
  • 3,138