Fibonacci difference equation: limiting ratio 1.6180

This is the Fibonacci equation $x(k+2) - x(k+1) - x(k) = 0$. Solve it by z-transform, then take the limit of the ratio.

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, 34, \dots$

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

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

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

Since $\left|\dfrac{z_2}{z_1}\right| = \dfrac{0.618}{1.618} = 0.382 < 1$, we get $\left(\dfrac{z_2}{z_1}\right)^k \to 0$ as $k \to \infty$:

$$\lim_{k\to\infty}\frac{x(k+1)}{x(k)} = z_1 = \frac{1+\sqrt5}{2} = 1.6180$$

This is the golden ratio.

Numerical check

The ratio oscillates about 1.6180 and settles there.

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