Fibonacci difference equation: series to 8 terms

This is the Fibonacci difference equation. Solve it by z-transform, then list the terms.

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

Step 5: Series up to the 8th term

From the closed form, or from the recursion $x(k+2) = x(k+1) + x(k)$:

Example check with the formula for $k = 7$: $\frac{1}{\sqrt5}\left[(1.618)^7 - (-0.618)^7\right] = \frac{1}{2.2361}\left[29.034 + 0.034\right] = 13.0$.

(If the series is counted from $k = 1$, the 8th term is $x(8) = 21$.)

Remarks

• One pole ($z = 1.618$) is outside the unit circle, so the sequence grows without bound.
• For large $k$ the second term dies out, so $x(k) \approx 0.4472(1.618)^k$. The ratio of successive terms tends to the golden ratio $1.6180$.

Answer: $x(k) = \dfrac{1}{\sqrt5}\left[\left(\dfrac{1+\sqrt5}{2}\right)^k - \left(\dfrac{1-\sqrt5}{2}\right)^k\right]$. Series: $0, 1, 1, 2, 3, 5, 8, 13$.