Skip to content

Recursion and induction

Recursion

A recursively defined function \(f\) needs two ingredients:

  • a base, where the function value \(f(n)\) is defined, for some value of \(n\).
  • a recursion, in which the computation of the function in \(n\) is explained with the help of the previous values smaller than \(n\).

For example, the sum

\[ \begin{align*}&\sum_{i=1}^1 i = 1,\\ &\sum_{i=1}^{n+1} i = (n + 1) + \sum_{i=1}^{n} i.\end{align*} \]

Or the product

\[ \begin{align*}&\prod_{i=0}^0 i = 1,\\ &\prod_{i=0}^{n+1} i = (n+1) \cdot \prod_{i=0}^{n} i.\end{align*} \]

Induction

Principle - Natural induction: suppose \(P(n)\) is a predicate for \(n \in \mathbb{Z}\), let \(b \in \mathbb{Z}\). If the following holds

  • \(P(b)\) is true,
  • for all \(k \in \mathbb{Z}\), \(k \geq b\) we have that \(P(k)\) implies \(P(k+1)\).

Then \(P(n)\) is true for all \(n \geq b\).

For example, we claim that \(\forall n \in \mathbb{N}\) we have

\[ \sum_{i=1}^n i = \frac{n}{2} (n+1). \]

We first check the claim for \(n=1\):

\[ \sum_{i=1}^1 i = \frac{1}{2} (1+1) = 1. \]

Now suppose that for some \(k \in \mathbb{N}\)

\[ \sum_{i=1}^k i = \frac{k}{2} (k+1). \]

Then by assumption

\[ \begin{align*} \sum_{i=1}^{k+1} i &= \sum_{i=1}^k i + (k+1), \\ &= \frac{k}{2}(k+1) + (k+1), \\ &= \frac{k+1}{2}(k+2). \end{align*} \]

Hence if the claim holds for some \(k \in \mathbb{N}\) then it also holds for \(k+1\). The principle of natural induction implies now that \(\forall n \in \mathbb{N}\) we have

\[ \sum_{i=1}^n i = \frac{n}{2}(n+1). \]

Principle - Strong induction: suppose \(P(n)\) is a predicate for \(n \in \mathbb{Z}\), let \(b \in \mathbb{Z}\). If the following holds

  • \(P(b)\) is true,
  • for all \(k \in \mathbb{Z}\) we have that \(P(b), P(b+1), \dots, P(k-1)\) and \(P(k)\) together imply \(P(k+1)\).

Then \(P(n)\) is true for all \(n \geq b\).

For example, we claim for the recursion

\[ \begin{align*} &a_1 = 1, \\ &a_2 = 3, \\ &a_n = a_{n-2} + 2 a_{n-1} \end{align*} \]

that \(a_n\) is odd \(\forall n \in \mathbb{N}\).

We first check the claim for for \(n=1\) and \(n=2\), from the definition of the recursion it may be observed that the it is true.

Now suppose that for some \(i \in \{1, \dots, k\}\) \(a_i\) is odd.

Then by assumption

\[ \begin{align*} a_{k+1} &= a_{k-1} + 2 a_k, \\ &= a_{k-1} + 2 a_{k} + 2(a_{k-2} + 2a_{k-1}), \\ &= 2 (a_k + a_{k-2} + 2 a_{k-1}) + a_{k-1}, \end{align*} \]

so \(a_{k+1}\) is odd.