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