Recurrence Equation｜Gao's Blog

Introduction
Solving Recurrence Relations for Fibonacci Numbers
Reference

Introduction

Sometimes we need to know the complexity of a recursive function, we usually use induction method (or sometimes is called substitution method), recursion-tree method and master theorem. However all these methods only give a big $\mathcal{O}$ uppper bound approximation. If we want to find a closed-form expression of recursive algorithm’s complexity we can solve recurrence equation using generating functions.

A famous example for the recurrence equation is for the Fibonacci numbers

$$
\begin{split}
f_0 &= 0\\\\
f_1 &= 1\\\\
f_n &= f_{n - 1} + f_{n - 2} \quad n \ge 2
\end{split}
$$

By using the generating functions one can obtained the closed-form expression for the complexity of a recursive algorithm by following these steps

Define some proper generating functions
Find the relationship between them
Solve the equations in terms of other generating functions
Find the coefficients using partial fractions and differentiation and obtain the closed-form expression

Solving Recurrence Relations for Fibonacci Numbers

Define Generating Functions

$$
G(x) \longleftrightarrow \langle f_0, f_1, f_2, f_3, \dots \rangle \longleftrightarrow \langle 0, 1, f_1 + f_0, f_2 + f_1, f_3 + f_2, \dots \rangle\\\\
$$

Find The Relationship

$$
\begin{split}
\langle 0, 1, 0, 0, 0, \dots \rangle & \longleftrightarrow x\\\\
\langle 0, f_0, f_1, f_2, f_3, \dots \rangle & \longleftrightarrow x \cdot G(x)\\\\
\langle 0, 0, f_0, f_1, f_2, \dots \rangle & \longleftrightarrow x^2 \cdot G(x)\\\\
\langle 0, 1 + f_0, f_1 + f_2, f_2 + f_1, f_3 + f_2, \dots \rangle & \longleftrightarrow x + x \cdot G(x) + x^2 \cdot G(x)\\\\
\end{split}
$$

Solve the equation

$$
\begin{split}
G(x) &= x + x \cdot G(x) + x^2 \cdot G(x)\\\\
G(x) &= \frac{x}{1 - x - x^2}
\end{split}
$$

Obtain closed-form expression

We can factor the denominator

$$
1 - x - x^2 = (1 - a_1 x) (1 - a_2 x)
$$

so we can calculate that

$$
\begin{split}
a_1 &= \frac{1 + \sqrt{5}}{2}\\\\
a_2 &= \frac{1 - \sqrt{5}}{2}\\\\
\end{split}
$$

then we can find $c_1$ and $c_2$ that satisfies

$$
\frac{x}{1 - x - x^2} = \frac{c_1}{1 - a_1 x} + \frac{c_2}{1 - a_2 x}
$$

after some calculates (see reference #1) we can know

$$
\begin{split}
c_1 + c_2 &= 0\\\\
-(c_1 a_2 + c_2 a_1) &= 1\\\\
\end{split}
$$

so we get

$$
\begin{split}
c_1 = \frac{1}{a_1 - a_2}\\\\
c_2 = \frac{-1}{a_1 - a_2}\\\\
\end{split}
$$

using partial fractions we know

$$
f_n = \frac{a_1^n}{\sqrt{5}} - \frac{a_2^n}{\sqrt{5}} = \frac{1}{\sqrt{5}} \Bigg( \Big( \frac{1 + \sqrt{5}}{2} \Big)^n - \Big( \frac{1 - \sqrt{5}}{2} \Big)^n \Bigg)
$$