Fibonacci difference equation: closed form and limit

This is the Fibonacci equation. The data are not fully consistent: with $x(0) = 0$ and $x(1) = 1$, the equation itself gives $x(2) = x(1) + x(0) = 1$, not 2. So $x(0) = 0$ and $x(1) = 1$ are taken as the initial conditions. A note at the end covers the case $x(2) = 2$.

Step 1: Take the z-transform

Use $\mathcal{Z}[x(k+2)] = z^2X(z) - z^2x(0) - zx(1)$ and $\mathcal{Z}[x(k+1)] = zX(z) - zx(0)$, with $x(0) = 0$ and $x(1) = 1$:

$$\left[z^2X(z) - z\right] - zX(z) - X(z) = 0$$ $$X(z) = \frac{z}{z^2 - z - 1}$$

Step 2: Factorise the denominator

$$z^2 - z - 1 = 0 \;\Rightarrow\; z_{1,2} = \frac{1 \pm \sqrt{5}}{2}, \quad z_1 = 1.6180,\; z_2 = -0.6180$$

Step 3: Partial fractions of $X(z)/z$

$$\frac{X(z)}{z} = \frac{1}{(z-z_1)(z-z_2)} = \frac{1}{z_1 - z_2}\left[\frac{1}{z-z_1} - \frac{1}{z-z_2}\right], \quad z_1 - z_2 = \sqrt{5}$$ $$X(z) = \frac{1}{\sqrt5}\left[\frac{z}{z - z_1} - \frac{z}{z - z_2}\right]$$

Step 4: General (closed-form) solution

$$x(k) = \frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^k - \left(\frac{1-\sqrt5}{2}\right)^k\right], \quad k = 0, 1, 2, \dots$$

Here $1/\sqrt5 = 0.4472$. Check: $x(0) = 0$, and $x(1) = \frac{1}{\sqrt5}\cdot\sqrt5 = 1$.

First terms: $0, 1, 1, 2, 3, 5, 8, 13, 21, \dots$

Step 5: Limiting value of $x(k+2)/x(k)$

Let $z_1 = 1.6180$ and $z_2 = -0.6180$:

$$\frac{x(k+2)}{x(k)} = \frac{z_1^{k+2} - z_2^{k+2}}{z_1^{k} - z_2^{k}} = \frac{z_1^2 - z_2^2\left(\dfrac{z_2}{z_1}\right)^{k}}{1 - \left(\dfrac{z_2}{z_1}\right)^{k}}$$

Since $|z_2/z_1| = 0.382 < 1$, the bracketed powers go to 0:

$$\lim_{k\to\infty}\frac{x(k+2)}{x(k)} = z_1^2 = \left(\frac{1+\sqrt5}{2}\right)^2 = \frac{3+\sqrt5}{2} = 2.6180$$

Note that $z_1^2 = z_1 + 1$ (from $z^2 - z - 1 = 0$), so the answer is $1.6180 + 1 = 2.6180$.

Numerical check: $x(10)/x(8) = 55/21 = 2.619$.

Note on $x(2) = 2$

If $x(1) = 1$ and $x(2) = 2$ are taken instead, the equation forces $x(0) = 1$. The sequence $1, 1, 2, 3, 5, \dots$ is the same series shifted by one step:

$$x(k) = \frac{1}{\sqrt5}\left[(1.618)^{k+1} - (-0.618)^{k+1}\right]$$

The limiting ratio is still $2.6180$, because the ratio depends only on the dominant root.

Answer: $x(k) = \dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^k - \left(\dfrac{1-\sqrt5}{2}\right)^k\right]$, and $\lim_{k\to\infty} x(k+2)/x(k) = 2.6180$.