---
title: "Fibonacci difference equation: closed form and limit"
subject: "Digital Control System"
chapter: 2
key: "semester_6/digital_control_system:fibonacci-general-solution"
source: https://www.bctengineer.com/q/semester_6/digital_control_system/fibonacci-general-solution
site: BCT Engineering
---

# Fibonacci difference equation: closed form and limit

Digital Control System · Chapter 2: The Z-Transform

- Asked in: 2072 Asoj, 8 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/digital_control_system/fibonacci-general-solution
- Whole chapter: https://www.bctengineer.com/md/semester_6/digital_control_system/chapter-2

## Question

Consider the difference equation x(k+2)=x(k+1)+x(k) where x(0)=0, x(1)=1 and x(2)=2. Obtain the general solution x(k) in a closed form. Find the limiting value of x(k+2)/x(k) when sequence variable approaches infinity.

## Short answer

Closed form from z-transform: x(k)=(1/√5)[((1+√5)/2)^k – ((1–√5)/2)^k]. As k→∞, x(k+2)/x(k) → φ^2 = (3+√5)/2 = 2.6180.

## Answer

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

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. With x(0)=0, x(1)=1, the z-transform gives X(z) = ?
   A. z^2/(z^2 - z - 1)
   B. z/(z^2 + z - 1)
   C. z/(z^2 - z - 1)
   D. 1/(z^2 - z - 1)
   Answer: C. z^2X - z - zX - X = 0. (Key point: Transform of difference equation)

2. Which is the closed form?
   A. The same with a plus sign
   B. The same without 1/sqrt5
   C. [(1+sqrt5)/2]^k only
   D. [(1+sqrt5)/2]^k - [(1-sqrt5)/2]^k all over sqrt5
   Answer: D. Partial fractions give 1/sqrt5 [z/(z-z1) - z/(z-z2)]. (Key point: Closed form)

3. Why are x(0)=0, x(1)=1 used instead of x(2)=2?
   A. The equation itself gives x(2) = 1 from them
   B. x(2) is always zero
   C. Three conditions are always needed
   D. x(2) is not allowed
   Answer: A. x(2) = x(1) + x(0) = 1. (Key point: Inconsistent data)

4. What is lim x(k+2)/x(k)?
   A. 0.382
   B. z1^2 = 2.618
   C. 1.618
   D. 1
   Answer: B. The dominant root gives z1^2 = z1 + 1 = 2.618. (Key point: Limit of x(k+2)/x(k))

## Close variants set in other exams

- [Third-order difference equation: limit x(k+2)/x(k)](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Athird-order-difference-limit-k) — Digital Control System, chapter 2, asked 2×

## Related in Digital Control System

- [Fibonacci difference equation: limiting ratio 1.6180](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Afibonacci-limit-ratio) — Digital Control System, chapter 2
- [Fibonacci difference equation: series to 8 terms](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Afibonacci-series-8-terms) — Digital Control System, chapter 2
- [Third-order difference equation: limit x(k+2)/x(k+1)](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Athird-order-difference-limit-k1) — Digital Control System, chapter 2
- [Difference equation with given input sequence](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Adifference-equation-given-inputs) — Digital Control System, chapter 2, asked 2×

## Related in other subjects

- [Characteristic form FD solution (velocity, pressure)](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acharacteristic-fd-velocity-pressure) — Computational Techniques in Civil Engineering, chapter 6, asked 2×