Informal Introduction

Recursion Relation is also know as Recursive Formula. Informal definition of recursion relation is the way to define series that each item defined by the previous items. But, to construct a complete recursion series, we need to define initial terms as precondition at first place. By its construction, it is easier to define rather than to answer what value of n in the series.

  • Fibonacci recurrence relation is:
    $$F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) \ \text{if} \ n \geq 2$$
    Formula for $F(n)$ which involve only n is:
    $$F(n) = \bigl(\frac{\Phi^n - (-\phi)^n)}{\sqrt5}\bigr) \ \text{where} \ \Phi = \frac{(\sqrt5+1)}{2} \text{and} \ \phi=\frac{(\sqrt5-1)}{2}$$

  • Find unique derangements of $n$ people sit in $\{s_i, s_j, ..., s_n\}$ where $i \neq j$. This problem has direct factorial formula (defined in Taylor series):
    $$D(n) = n!(\frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - ... \frac{(-1)^n}{n!}), \ if \ n > 2$$
    The recursion formula is:
    $$D(n) = (n - 1) (D(n-1) + D(n-2))$$
    Formula for $D(n)$ is:
    $$D(n) = n D(n-1) + (-1)^n$$

Further introductory can be explored in Recurrence Relations & Generating Functions by R. Knott

Geometric Series

For $r \neq 1$, the sum of the first n of geometric series is:

$$a+ar+ar^{2}+ar^{3}+ \cdots +ar^{n-1}=\sum_{k=0}^{n-1}ar^{k}=a\left({\frac{1-r^{n}}{1-r}}\right)$$

PROOF: a is initial term and r is common ratio.

$$\eqalign{ s&=a+ar+ar^{2}+ar^{3}+\cdots +ar^{n-1},\\ rs&=ar+ar^{2}+ar^{3}+ar^{4}+\cdots +ar^{n},\\ s-rs&=a-ar^{n},\\s(1-r)&=a(1-r^{n}), }$$

So:

$${\displaystyle s=a\left({\frac {1-r^{n}}{1-r}}\right)\quad {\text{(if }}r\neq 1{\text{)}}.}$$

As n goes to infinity, the absolute value of r must be less than one for the series to converge. The sum then becomes:

$$a+ar+ar^{2}+ar^{3}+ar^{4}+\cdots =\sum _{k=0}^{\infty }ar^{k}={\frac {a}{1-r}},{\text{ for }}|r|<1.$$

When a = 1, this can be simplified to:

$$1\,+\,r\,+\,r^{2}\,+\,r^{3}\,+\,\cdots \;=\;{\frac {1}{1-r}},$$

the left-hand side being a geometric series with common ratio r.

The formula also holds for complex r, with the corresponding restriction, the modulus of r is strictly less than one.

Proof of Convergence

We can prove that the geometric series converges using the sum formula for a geometric progression:

$${\displaystyle {\begin{aligned}1+r+r^{2}+r^{3}+\cdots \ &=\lim _{n\rightarrow \infty }\left(1+r+r^{2}+\cdots +r^{n}\right)\\&=\lim _{n\rightarrow \infty }{\frac {1-r^{n+1}}{1-r}}.\end{aligned}}}$$

Since $(1 + r + r^2 + ... + r^n)(1−r) = 1−r^{n+1}$ and $r^{n+1} \rightarrow 0 \ \text{for} \ |r| < 1$

Convergence of geometric series can also be demonstrated by rewriting the series as an equivalent telescoping series. Consider the function,

$$g(K)={\frac {r^{K}}{1-r}}$$

Note that

$${\displaystyle 1=g(0)-g(1)\ ,\ r=g(1)-g(2)\ ,\ r^{2}=g(2)-g(3)\ ,\ldots }$$

Thus,

$${\displaystyle S=1+r+r^{2}+r^{3}+\cdots =(g(0)-g(1))+(g(1)-g(2))+(g(2)-g(3))+\cdots .}$$

If,

$$|r| < 1$$

then

$$g(K)\longrightarrow 0{\text{ as }}K\to \infty$$

so S converges to:

$$g(0)={\frac {1}{1-r}}$$

Binomial Theorem (Factorial Method)

Let $n$ be a positive integer, and $x$ and $y$ real numbers (or complex numbers, or polynomials). The coefficient of $x^ky^{n-k}$, in $k^{th}$ term in the expansion of $(x+y)^n$, is equal to ${n \choose k}$, where:

$${n \choose k} = \frac{n!}{(n-k)!k!}$$

So the Binomial Expansion is:

$$(x+y)^n = \sum_{r=0}^n {n \choose r} x^{n-r} y^r = \sum_{r = 0}^n {n \choose r} x^r y^{n-r}$$

PROOF:

$$ \begin{align} (x+y)^n &= (x+y)(x+y)^{n-1} \\ &= (x+y)\bigg(\binom{n-1}{0} x^{n-1} + \binom{n-1}{1} x^{n-2}y + \cdots + \binom{n-1}{n-1}y^{n-1}\bigg) \\ &= x^n + \left( \binom{n-1}{0} + \binom{n-1}{1} \right) x^{n-1}y + \left( \binom{n-1}{1} + \binom{n-1}{2} \right) x^{n-2}y^2 \phantom{=} + \cdots + \left(\binom{n-1}{n-2} + \binom{n-1}{n-1} \right) xy^{n-1} + y^n \\ \end{align} $$

and now Pascal's identity applies:

$$\binom{n-1}{k-1}+\binom{n-1}{k} = \binom{n}{k}$$

So the right side simplifies to:

$$x^n + \binom{n}{1} x^{n-1}y + \binom{n}{2} x^{n-2}y^2 + \cdots + \binom{n}{n-1}xy^{n-1} + y^n$$

First Order Recurrences

The simplest type of recurrence reduce immediately to a product. The recurrence:

$$a_n = x_na_{n-1} \qquad \text{for} \ n>0 \ \text{with} \ a_0 = 1$$

equivalent to:

$$a_n = \prod_{1 \leq k \leq n} x_k$$

Theorem 2.1 (First Order linear Recurrences)

The recurrence

$$a_n = x_na_{n-1} + y_n \qquad \text{for} \ n>0 \ \text{with} \ a_0 = 0$$

has the explicit solution:

$$a_n = y_n + \sum_{1 \leq j < n}y_jx_{j+1}x_{j+2}...x_n$$

PROOF. Dividing both sides by $x_nx_{n-1}...x_1$ and iterating, we have:

$$ \eqalign{ a_n &= x_nx_{n-1}...x_1 \sum_{1 \leq j \leq n}\frac{y_j}{x_jx_{j-1}...x_1}\\ &= y_n + \sum_{1 \leq j < n}y_jx_{j+1}x_{j+2}...x_n } $$

Nonlinear First-Order Recurrences

Simple convergence. One convincing reason to calculate initial values is that many recurrences with a complicated appearance simply converge to a constant. For example:

$$a_n = \frac{a}{(1+a_{n-1})} \qquad for \ n>0 \ with \ a_0 = 1$$

This is a so-called continued fraction equation, which is discussed in §2.5. By calculating initial values, we can guess that the recurrence converges to a constant:

Each iteration increases the number of significant digits available by a constant number of digits (about half a digit). is is known as simple convergence. If we assume that the recurrence does converge to a constant, we know that the constant must satisfy $\alpha = \frac{1}{(1+\alpha)}$, or $1 - \alpha - \alpha^2 = 0$, which leads to the solution $\alpha = \frac{(\sqrt{5}-1)}{2} \approx .6180334$.

Higher-Order Recurrences

Recurrences where the right-hand side of the equation for $a_n$ is a linear combination of $a_{n-1}, a_{n-2},$ and so on.

For example:

$$a_n = 3a_{n-1} - 2a_{n-2} \qquad for \ n>1 \ with \ a_0 = 0 \ and \ a_1=1$$

Solution:

$$ \eqalign{ a_n - a_{n-1} &= 2(a_{n-1} - 2_{n-2})\\ &= 2^{n-1}\\ a_n &= 2^{n}-1\\ } $$

Another example:

$$a_n = 5a_{n-1} - 6a_{n-1} \qquad for \ n>1 \ with \ a_0 = 0 \ and \ a_1=1$$

Has solution:

$$ \eqalign{ a_n - 3a_{n-1} &= 2(a_{n-1} - 3_{n-2})\\ &= 2^{n-1}\\ a_n &= 3^n - 2^n } $$

Theorem 2.2 (Linear recurrences with constant coefficients)

$$a_n = x_1a_{n-1}+x_2a_{n-2}+...+x_ta_{n-t} \qquad for \ n \geq \ t$$

Can be expressed as a linear combination (with coefficients depending on the initial conditions $a_0,a_1,...,a_{t-1}$):

$$q(z) \equiv z^t - x_1z^{t-1} - x_2z^{t-2} - ... - x_t$$

PROOF. For $a_n = \beta^n$, where $\beta$ is a root of the "characteristic polynomial":

$$\beta^n = x_1\beta^{n-1} + x_2\beta^{n-2} + ... + x_t\beta^{n-t} \qquad for \ n \geq t$$

or, equivalently,

$$\beta^{n-t}q(\beta) = 0$$

That is, $\beta^n$ is a solution to the recurrence for any root $\beta$ of the characteristic polynomial.

Finding the coefficients. Develop theorem 2.2 to create a system of simultaneously equations that can be solved to yield the constants in the linear combination. For example:

$$a_n = 5a_{n-1} - 6a_{n-2} \qquad for \ n \geq 2 \ with a_0 = 0 \ and \ a_1 = 1$$

The characteristic equation is $z^2 - 5z + 6 = (z-3)(z-2)$, so:

$$a_n = c_03^n + c_12^n$$

Matching this formula against the values at $n = 0$ and $n = 1$, we have:

$$a_0 = 0 = c_0 + c_1$$$$a_1 = 1 = 3c_0 + 2c_1$$

The solution to these simultaneous equations is $c_0 = 1$ and $c_1 = -1$, so $a_n = 3^n - 2^n$

Degenerate cases. When the coefficients turn out to be zero and/or some roots have the same modulus, the result can be somewhat counterintuitive. For example:

$$a_n = 2a_{n-1} - a_{n-2} \qquad for \ n \geq 2 \ with \ q_0 = 1 \ and \ a_1 = 2$$

The characteristic equation is $z^2 - 2z + 1 = (z-1)^2$, so:

$$a_n = c_01^n + c_1n1^n$$

We have:

$$a_0 = 1 = c_0$$$$a_1 = 2= c_0 + c_1$$

gives $c_0 = c_1 = 1$, so $a_n = n + 1$.

Fibonacci numbers. ${0, 1, 1, 2, 3, 4, 8, 13, ...}$ is defined by prototypical second-order recurrence:

$$F_n = F_{n-1} + F_{n-2} \qquad for \ n>1 \ with \ F_0 = 0 \ and \ F_1 = 1$$

roots of $u^2-u-1 = \phi = (1+\sqrt(5)/2 = 1.61803..$ and $\hat{\phi} = (1-\sqrt(5)/2 = -.61803...)$, Theorem 2.2 says that the solution is:

$$F_N = c_0\phi^N+c_1\hat{\phi}^N$$

for some constants $c_0$ and $c1$:

$$F_0 = 0 = c_0 + c_1$$$$F_1 = 1 = c_0\phi + c_1\hat{\phi}$$

yield the solution:

$$F_N = \frac{1}{\sqrt{(5)}}(\phi^N - \hat{\phi}^N)$$

Nonconstant coefficients. If the coefficients are not constants, then more advanced technique are needed because Theorem 2.2 does not apply. For example:

$$\eqalign{ a_n &= na_{n-1} + n(n-1)a_{n-2} \qquad for \ n>1 \ with \ a_1 = 1 \ and \ a_0 = 0\\ \frac{a_n}{n!} &= \frac{na_{n-1} + n(n-1)a_{n-2}}{n!}\\ a_n &= n!F_n\\ }$$

Method for Solving Recurrences

Change of Variables

For example:

$$a_n = \sqrt{a_{n-1}a_{n-2}} \qquad for \ n>1 \ with \ a_0 = 1 \ and \ a_1 = 2$$

Let $b_n = lga_n$:

$$b_n = \frac{1}{2}(b_{n-1} + b_{n-2}) \qquad for \ n>1 \ with \ b_0 = 0 \ and \ b_1 = 1$$



Another example, for recurrence to continued fractions:

$$a_n = \frac{1}{(1+a_{n-1})} \qquad for \ n>0 \ with \ a_0 = 1$$

Iterating this recurrence gives the sequence:

$$\eqalign{ a_0 &= 1\\ a_1 &= \frac{1}{1+1} = \frac{1}{2}\\ a_2 &= \frac{1}{1 + \frac{1}{1+1}} = \frac{1}{1+\frac{1}{2}} = \frac{2}{3}\\ a_3 &= \frac{1}{1+\frac{1}{1 + \frac{1}{1+1}}} = \frac{1}{1+\frac{2}{3}} = \frac{3}{5} }$$

That form, reveals the Fibonacci numbers. Let $a_n = b_{n-1} / b_n$:

$$\frac{b_{n-1}}{b_n} = 1 / (1 + \frac{b_{n-2}}{b_{n-1}}) \qquad for \ n > 1 \ with \ b_0 = b_1 = 1$$

Dividng both sides by $b_{n-1}$ gives:

$$\frac{1}{b_n} = \frac{1}{b_{n-1} + b_{n-2}} \qquad for \ n > 1 \ with \ b_0 = b_1 = 1$$

Repertoire

$$a_n = (n-1)a_{n-1}-na_{n-2}+n+1 \qquad for \ n>1 \ with \ a_0 = a_1 = 1$$

Introducing a quantity $f(n)$ to the right-hand side:

$$a_n = (n-1)a_{n-1}-na_{n-2}+f(n)$$

We arrive at the table:

$a_n$ $f(n)$
1 2
$n$ n - 1
$n^2$ n + 1

Subtracting the first row form the third gives the result that means that:

$$a_n = n^2 - 1 \qquad when \qquad f(n) = n-1\\ initial \ condition \ a_0 = -1 \ and \ a_1 = 0$$

Now, we have two (linearly independent) solutions for $f(n) = n - 1$, which we combine to get the right initial values, yielding the result:

$$a_n = n^2 - n + 1$$

Bootstapping

Given Fibonacci recurrence:

$$a_n = a_{n-1} + a_{n-2} \qquad for \ n > 1 \ with a_0 = 0 \ and a_1 = 1$$

Note, that $a_n$ is increasing. Therefore, $a_{n-1} > a_{n-2}$ and $a_n > 2a_{n-2}$. Iterating this inequality imply the lower bound:

$$a_n > 2^{n/2}$$

On the other hand, $a_{n-2} > a_{n-1}$ and $a_n < 2a_{n-1}$. Iterating this inequality imply the upper bound:

$$a_n < 2^{n}$$

"guessing" a solution of the form $a_n \sim c_0\alpha^n$, with $\sqrt(2) < \alpha < 2$

Perturbation

$$a_{n+1} = 2a_n + \frac{a_{n-1}}{n^2} \qquad for \ n>1 \ with \ a_0=1 \ and \ a_1 = 2$$

Eliminate $\frac{1}{n^2}$ because makes only a small constribution to recurrence, so:

$$a_{n+1} \approx 2a_n$$

This a growth of the rough form $a_n \approx 2^n$ is anticipated. To make this preciese, consider the simpler sequence:

$$b_{n+1} = 2b_n \qquad for \ n>0 \ with \ b_0=1$$

(so that $b_n = 2^n$) and compare the two recurrence by forming the ratio:

$$\rho_n = \frac{a_n}{b_n} = \frac{a_n}{2^n}$$

From the recurrences, we have:

$$\rho_{n+1} = \rho_n + \frac{1}{4n^2} \rho_{n-1} \qquad for \ n>0 \ with \ \rho_0=1$$

Clearly, the $\rho_n$ are increasing. To prove they tend to a constant, note that:

$$\rho_{n+1} \leq \rho_n (1+\frac{1}{4n^2}) \qquad for \ n \geq 1 \ so \ that \qquad \rho_{n+1} \leq \Pi_{k=1}^n (1+\frac{1}{4k^2})$$

But the infinite product corresponding to the right-hand side converges monotonically to:

$$\alpha_0 = \Pi_{k=1}^\infty (1 + \frac{1}{4k^2}) = 1.46505...$$

This, $\rho_n$ is bounded from above by $\alpha_0$ and, as it is increasing, it must converge to a constant. We have thus proved that:

$$a_n \sim \alpha \cdot 2^n$$

for some constant $\alpha \le 1.46505...$

Binary Divide-and-Conquer Recurrences and Binary Numbers

The number of comparisons used by mergesort is given by the solution to the recurrence:

$$C_N=C_{\lfloor{N/2}\rfloor}+C_{\lceil{N/2}\rceil}+N \qquad for \ N > 1 \ with \ C_1=0 \qquad (4)$$


Binary Search

The number comparisons used during an unsuccessful search with binary search in a table of size N in the worst case is equal to the number of bits in the binary representation of N.

$$B_N = B_{\lfloor{N/2}\rfloor}+1 \qquad for \ N \geq 2 \ with \ B_1 = 1$$

Which exact solution is:

$$B_N = \lfloor{lgN}\rfloor + 1$$

Exact solution of mergesort recurrence

The mergesort recurrence (4) is easily solved by differencing: if $D_N$ is defined to be $C_{N+1} - C_N$, the $D_N$ satisfied the recurrence:

$$D_N = D_{\lfloor{N/2}\rfloor}+1 \qquad for \ N \geq 2 \ with \ D_1 = 2$$

which iterates to:

$$D_N = {\lfloor{lgN}\rfloor}+2$$

and, therefore,

$$C_N = N - 1 + \sum_{1 \leq k < N} ({\lfloor{lgk}\rfloor}+1)$$

Theorem 2.4 (Mergesort). The number of comparison used by mergesort is equal to $N - 1$ plus the number of bits in the binary representations of all the numbers less than $N$. Both quantities are described by the recurrence:

$$C_N=C_{\lfloor{N/2}\rfloor}+C_{\lceil{N/2}\rceil}+N \qquad for \ N \geq 2 \ with \ C_1=0$$

Which has the exact solution $C_N = N{\lfloor{lgN}\rfloor} + 2N - 2^{{\lfloor{lgN}\rfloor} + 1}$.

PROOF

$$ \eqalign{ C_N &= (N-1) + (N-1) + (N-2) + (N-4) + ... + (N - 2^{{\lfloor{lgN}\rfloor} + 1})\\ &= (N-1) + N({\lfloor{lgN}\rfloor} + 1) - (1 + 2 + 4 + ... + 2^{{\lfloor{lgN}\rfloor} + 1})\\ &= N{\lfloor{lgN}\rfloor} + 2N - 2^{{\lfloor{lgN}\rfloor} + 1} } $$

General Divide-and-Conquer Recurrences

A variety of "devide-and-conquer" recurrence qrise that depend on the number and relative size of subproblems, the extent to which they overlap, and the cost of recombining them for the solution.

In pursuit of general solution, we start with the recursive formula:

$$\alpha(x) = \alpha a (x/\beta) + f(x) \qquad for \ x>1 \ with \ a(x) = 0 \ for \ x \leq 1$$

defining a function over the positive real numbers. In essence, this corresponds to a divide-and-conquer algorithm that divides a problem of size x into $\alpha$ subproblems of size $x/\beta$ and recombines them at a cost of $f(x)$.

For example, consider the case where $f(x)=x$ and we restrict ourselces to the integers $N=\beta^n$. We have:

$$\alpha_{\beta n} = \alpha a_{\beta n - 1} + \beta^n \qquad for \ n > 0 \ with \ a_1 = 0$$

Dividing both sides by $\alpha^n$ and iterating, we have the solution:

$$\alpha_{\beta n} = \alpha^n \sum_{1 \leq j \leq n} \left(\frac{\beta}{\alpha}\right)^j$$

Theorem 2.5 (Divide-and-conquer functions). If the function $a(x)$ satisfies the recurrence:

$$a(x) = \alpha a (x/\beta) + x \qquad for \ x > 1 \ with \ a(x) = 0 \ for \ x \leq 1$$

then

$$ \eqalign{ if \ \alpha < \beta &\qquad a(x) \sim \frac{\beta}{\beta-\alpha}x\\ if \ \alpha = \beta &\qquad a(x) \sim xlog_{\beta}x\\ if \ \alpha > \beta &\qquad a(x) \sim \frac{\alpha}{\alpha-\beta}\left(\frac{\beta}{\alpha}\right)^{{log_{\beta}\alpha}} x^{log_{\beta}\alpha} } $$

Master Theorem

Divide-and-conquer algorithms

Suppose that an algorithm attacks a problem of size $N$ by:

  • Dividing into $\alpha$ parts of size about $N/\beta$
  • Solving recursively
  • Combining solutions with extra cost $\theta(N^{\gamma}(log N)^{\delta})$
  1. Mergesort ($\alpha = 2, \ \beta = 2, \ \gamma = 1, \ \delta = 0$)
    $$C_N = 2C_{N/2}+N$$

  2. Batcher network ($\alpha = 2, \ \beta = 2, \ \gamma = 1, \ \delta = 1$)
    $$C_N = 2C_{N/2} + NlgN$$

  3. Karatsuba multiplication ($\alpha = 3, \ \beta = 2, \ \gamma = 1, \ \delta = 0$)
    $$C_N = 3C_{N/2}+N$$

  4. Strasses matrix multiply ($\alpha = 7, \ \beta = 2, \ \gamma = 1, \ \delta = 0$)
    $$C_N = 7C_{N/2}+N$$