5.2. Recursive Sequences and the Principle of Induction
Choosing ${\mathbb{N}}^{\ast}$ as domain for our sequences has a wide effect mainly due to the well advanced arithmetic and ordering properties that come with the natural numbers.
This structure is settled when constructing $\mathbb{N}$ in set theory. From there we take the following characterization of $\mathbb{N}$:
Proposition:

$k\in \mathbb{N}\Rightarrow k=0\vee k=n+1$ for a suitable $n\in \mathbb{N}$.

Every nonempty subset of $\mathbb{N}$ has a smallest element.


[5.2.1] 

That means:

Every nonzero natural number is the successor of another natural number.

Every nonempty collection of natural numbers has a first one.
Both of these properties already support the idea to get every natural number by successive counting starting with 0. The Principle of Induction makes this precise:
Proposition (Principle of Induction): Let A be an arbitrary subset of $\mathbb{N}$ so that

$0\in A$

$n\in A\Rightarrow n+1\in A$


[5.2.2] 
Then A is the whole of $\mathbb{N}$, i.e.: $A=\mathbb{N}$.
Proof: We proceed indirectly and assume: $A\ne \mathbb{N}$. Then the difference $\mathbb{N}\backslash A$ is a nonempty subset of $\mathbb{N}$ and, following 2. in [5.2.1], has a smallest element, say $k\in \mathbb{N}\backslash A$. From $0\in A$ we conclude that $k\ne 0$. According 1. in [5.2.1] we find a number $n\in \mathbb{N}$ so that $k=n+1$. Especially we have $n<k$. As k is the smallest element of $\mathbb{N}\backslash A$ we thus know that n is no member of $\mathbb{N}\backslash A$. But that means $n\in A$ and from the second condition in [5.2.2] we can conclude that $k=n+1$ belongs to A. contradiction!

The induction principle is a very effective tool. A whole technique called proof by induction, is based on this principle.
We take the proof of a so called summation formula as a first example to demonstrate this technique:
Adding the odd intergers from 1 to $2n+1$ gives the following results for the different values of n:
n = 0 
n = 1 
n = 2 
n = 3 
n = 4 
n = 5 
1
= 1 
1 + 3
= 4 
1 + 3 + 5
= 9 
1 + 3 + 5 + 7
= 16 
1 + 3 + 5 + 7 + 9
= 25 
1 + 3 + 5 + 7 + 9 + 11
= 36 
Obviously each of the six results is a square number, namely the square of n + 1, the number of addends!
We would gain an enormous advantage, especially for huge numbers, if this would be true for every n.
Unfortunately however this assumption could not be proved the customary way because we have to prove infinitely many single assertions.
But exactly that is performed by the induction principle.
Example: For all $n\in \mathbb{N}$ we have:
$\sum _{i=0}^{n}(2i+1)={(n+1)}^{2}$

[5.2.3] 
Proof:
Our task is, a bit awkwardly shaped, the following: Show that the set
$A\u2254\{n\in \mathbb{N}\sum _{i=0}^{n}(2i+1)={(n+1)}^{2}\}\subset \mathbb{N}$,
i.e. the collection of all natural numbers satisfying [5.2.3] is all of $\mathbb{N}$. But to that end we only need to check if the two conditions of the induction principle hold for A!
The principle of induction now guarantees: $A=\mathbb{N}$. In other words our summation formular is actually true for all natural numbers.

Consider:
The just performed technique, splitting off the last addend,
$\sum _{i=0}^{n+1}(2i+1)=\sum _{i=0}^{n}(2i+1)+\sum _{i=n+1}^{n+1}(2i+1)=\sum _{i=0}^{n}(2i+1)+2(n+1)+1$
is the standard trick for sums and related expressions.
With proofs by induction it is a valuable advantage that the sentence to be proved  in our example the equation $\sum _{i=0}^{n+1}(2i+1)={(n+1+1)}^{2}$  can be noted just from the start by inserting n + 1 for n.
We practise the principle of induction with further summation formulas and other examples. We do this however without
the explicit formation of the set A and take the terms
${0\in A}$ resp. ${n\in A\Rightarrow n+1\in A}$
only as a label for the two steps in a proof by induction:

${0\in A}$ for the base step

${n\in A\Rightarrow n+1\in A}$ for the induction step.

Proposition (Summation formula for the geometric series): Let $q\in \mathbb{R},q\ne 1$, then every $n\in \mathbb{N}$ satisfies:
$\sum _{i=0}^{n}{q}^{i}=\frac{1{q}^{n+1}}{1q}$

[5.2.4] 
Proof:

The summation formula for the geometric series playes a very important role in calculus.
This is also true for the generalization of common binomial formula which we will present in the next proposition.
For the notation we need the binomial coefficients $(\phantom{T}\begin{array}{c}n\\ i\end{array})\phantom{T}$, for the slightly extensive proof we need two of their properties and a trick called index shift.
Proposition (Generalized Binomial Theorem): Let $a,b\in \mathbb{R}$, then
$(a+b)}^{n}=\sum _{i=0}^{n}(\phantom{T}\begin{array}{c}n\\ i\end{array})\phantom{T}{a}^{ni}{b}^{i$

[5.2.5] 
holds for every $n\in \mathbb{N}$.
Proof:

Summation formulas are by far not the only sentences to be proved by induction. The following example deals with an inequality.
Proposition (Bernoulli Inequality): For every real number $x\ge 1$ and any $n\in \mathbb{N}$ we have:
Proof:
${0\in A}:{(1+x)}^{0}=1\ge 1=1+0\cdot x$.
${n\in A\Rightarrow n+1\in A}:$Assume the inequality ${(1+x)}^{n}\ge 1+nx$ is already valid. Multiplying with the (due to $x\ge 1$) positive number $1+x$ gives:
${(1+x)}^{n}(1+x)\ge (1+nx)(1+x)$.
Thus we can argue as follows::
$\begin{array}{cc}\hfill {(1+x)}^{n+1}& ={(1+x)}^{n}(1+x)\hfill \\ \hfill & \ge (1+nx)(1+x)\hfill \\ \hfill & =1+nx+x+n{x}^{2}\hfill \\ \hfill & \ge 1+nx+x\text{,note that}n{x}^{2}\ge 0\hfill \\ \hfill & =1+(n+1)x\text{.}\hfill \end{array}$

The initial value 0 used with principle of induction is determind by the set $\mathbb{N}$. However we can modify the induction principle so that any integer k gets the option for the initial value:
Proposition: Let $k\in \mathbb{Z}$ and A be any subset of ${\mathbb{Z}}^{\ge k}$ so that

$k\in A$

$n\in A\Rightarrow n+1\in A$


[5.2.7]  then we have: $A={\mathbb{Z}}^{\ge k}$.
Proof: Let us set $A\text{'}\u2254\{iki\in A\}$. A' then is a subset of $\mathbb{N}$ containing 0 and with every n the successor $n+1$ as well.
From the induction principle we have $A\text{'}=\mathbb{N}$ and thus $A={\mathbb{Z}}^{\ge k}$.

Very close related to the induction principle is a certain construction method, often used with sequences, the so called definition by recursion.
We need two steps for a sequence $({a}_{n})$ to be constructed in this way:
The initial step is to fix a value for the first sequence member ${a}_{1}$. The second step is to introduce a general method to calculate any sequence member ${a}_{n+1}$ from its predecessor ${a}_{n}$. As an example the sequence $({a}_{n})$ could be constructed by the statement:
${a}_{1}\u22541\wedge {a}_{n+1}\u22542{a}_{n}\text{.}$
From the recursion formula we see that every new sequence member is twice its predecessor. So we can calculate the sequence members one after the other:
$({a}_{n})=(\mathrm{1,2,4,8,16,32,}\dots )\text{.}$
The following proposition introduces the
Principle of Recursion.
Proposition (Principle of Recursion): For any $c\in A$ and any function $f:{\mathbb{N}}^{\ast}\times A\to A$ the statement
${a}_{1}\u2254c\wedge {a}_{n+1}\u2254f(n,{a}_{n})$

[5.2.8] 
defines a sequence in A.
Proof: We need to show that [5.2.8] constitutes a function $a:{\mathbb{N}}^{\ast}\to A$. First we show that every $n\in \mathbb{N}$ has got an image in A. We set
$D\u2254\{n\in {\mathbb{N}}^{\ast}\text{there is an element}{a}_{n}\in A\text{according to}\text{[5.2.8]}\}$.
As ${a}_{1}\in A$ is guaranted by the premise we have $1\in D$. Now if $n\in D$, i.e. ${a}_{n}\in A$ the recursion formula assigns an element of A to the successor $n+1$, but that means $n+1\in D$. Thus we have $D={\mathbb{N}}^{\ast}$ according to the (generalized) induction principle.
Next we show that there is only one image for each n, applying the induction principle again: For the set
$E\u2254\{n\in {\mathbb{N}}^{\ast}\text{there is only one element}{a}_{n}\in A\text{according to}\text{[5.2.8]}\}$
we have: $1\in E$, because there is no $n\in {\mathbb{N}}^{\ast}$ such that $1=n+1$, so that there is no assignment in [5.2.8] except for ${a}_{1}=c$. Now let $n\in E$, thus ${a}_{n}$ is uniquely determined and so is $f(n,{a}_{n})$ (because f is a function!). Finally $n+1$ has only one predecessor, namely n. From all that we conclude that ${a}_{n+1}$ is uniquely determined, thus $n+1$ also belongs to E which completes our induction and we have $E={\mathbb{N}}^{\ast}$.

Consider:

We rarely use the explicit data c and f to define a sequence recursively. It is common to note them just the way we did in our introductory example. Either notion however can be translated into the other.
E.g. the statement ${a}_{1}=1\wedge {a}_{n+1}=2{a}_{n}$ turns into:
$c=1$ and $f:{\mathbb{N}}^{\ast}\times \mathbb{R}\to \mathbb{R}$ given by $f(n,x)=2x$.
Vice versa the data, let's say $c=0$ and $f:{\mathbb{N}}^{\ast}\times \mathbb{R}\to \mathbb{R}$ given by $f(n,x)=n+x$, translate to
${a}_{1}=0\wedge {a}_{n+1}=n+{a}_{n}$.

As with the induction principle and with the sequences, the principle of recursion is extendable to functions of the type $f:{\mathbb{Z}}^{\ge k}\times A\to A$.
The real advantage of recursive sequences lies in their ability to reflect dynamic situations.
Let's say a certain species of bacteria needs one hour to double its stock. Starting with one bacterium we can perfectly calculate the number
${a}_{n}$ of bacteria living at the beginning of the der nth hour by our initial recursive sequence.
As a clear disadvantage with recursive sequences we see the effort that is needed to calculate sequence members far from the start.
To get e.g. the size of the bacteria population when 100 hours are over you need to calculate separately 100 sequence members before!
We practise the principle of recursion with some examples. Note that changing only the first sequence member could result in a complete different sequence.
Example:
${a}_{1}\u22542\wedge {a}_{n+1}\u22543{a}_{n}2$ gives the sequence $(\mathrm{2,4,10,28,82,}\dots )$ , because
${a}_{2}=3{a}_{1}2=3\cdot 22=4$,
${a}_{3}=3{a}_{2}2=3\cdot 42=10$,
${a}_{4}=3{a}_{3}2=3\cdot 102=28\dots $

${a}_{1}\u22541\wedge {a}_{n+1}\u22543{a}_{n}2$ gives the sequence $(\mathrm{1,1,1,1,1,1,}\dots )$
.

$a}_{1}\u2254\frac{1}{2}\wedge {a}_{n+1}\u2254\frac{1}{{a}_{n}+1$ gives the sequence $(\frac{1}{2},\frac{2}{3},\frac{3}{5},\frac{5}{8},\frac{8}{13},\dots )$ .

${a}_{0}\u22541\wedge {a}_{n+1}\u2254{a}_{n}\cdot (n+1)$ produces the sequence of factorials:
${(\mathrm{1,1,2,6,24,120,720,5.040,}\dots )}_{n\ge 0}={(n!)}_{n\ge 0}$ .

Two special recursive sequences get names of their own.
Definition: Let $c,d,q\in \mathbb{R}$. A recursive sequence ${({a}_{n})}_{n\ge 0}$ of the shape

${a}_{0}\u2254c\wedge {a}_{n+1}\u2254{a}_{n}+d$
is called arithmetic.

[5.2.9] 

${a}_{0}\u2254c\wedge {a}_{n+1}\u2254{a}_{n}\cdot q$
is called geometric.

[5.2.10] 

Consider:
Proposition:

${({a}_{n})}_{n\ge 0}$ is arithmetic
$\iff $there is a $d\in \mathbb{R}$, such that ${({a}_{n})}_{n\ge 0}={({a}_{0}+nd)}_{n\ge 0}$ .

[5.2.11] 

${({a}_{n})}_{n\ge 0}$ is geometric
$\iff $there is a $q\in \mathbb{R}$, such that ${({a}_{n})}_{n\ge 0}={({a}_{0}\cdot {q}^{n})}_{n\ge 0}$ .

[5.2.12] 
Proof: We concentrate on 1. The second assertion is just a multiplicative version of the first one.
We split the equivalence into two parts.
"$\Rightarrow $": Let c and d be reals such that
${a}_{0}=c\wedge {a}_{n+1}={a}_{n}+d$.
Now we show by induction: ${a}_{n}={a}_{0}+nd$ for all $n\in \mathbb{N}$.
"$\Leftarrow $": Setting
${b}_{0}\u2254{a}_{0}\wedge {b}_{n+1}\u2254{b}_{n}+d$,
gives an arithmetic sequence ${({b}_{n})}_{n\ge 0}$ that satisfies the equality ${({b}_{n})}_{n\ge 0}={({b}_{0}+nd)}_{n\ge 0}$ as demonstrated just before. From that we have:
${({a}_{n})}_{n\ge 0}={({a}_{0}+nd)}_{n\ge 0}={({b}_{0}+nd)}_{n\ge 0}={({b}_{n})}_{n\ge 0}$ ,
so that ${({a}_{n})}_{n\ge 0}$ coincides with an arithmetic sequence and thus is arithmetic itself.

Arithmetic and geometric sequences show are some interesting properties.

As ${a}_{n+1}={a}_{n}+d\iff {a}_{n+1}{a}_{n}=d$, the difference of two consecutive members of an arithmetic sequence is a constant.:
${({a}_{n})}_{n\ge 0}$ is arithmetic$\iff {a}_{n+1}{a}_{n}=d\text{for all}n\in \mathbb{N}$.
Below we show: The members of an arithmetic sequence are the arithmetic mean of their neighbours.

As ${a}_{n+1}={a}_{n}\cdot q\iff \frac{{a}_{n+1}}{{a}_{n}}=q$ the quotient of two consecutive members of geometric sequence in ${\mathbb{R}}^{\ne 0}$ a constant:
${({a}_{n})}_{n\ge 0}$ is geometric$\iff \frac{{a}_{n+1}}{{a}_{n}}=q\text{for all}n\in \mathbb{N}$.
Next we show: The absolute value of a member of a geometric sequence is the geometric mean of its neighbours.
Proposition:

${({a}_{n})}_{n\ge 0}$ is arithmetic$\iff {a}_{n+1}=\frac{{a}_{n}+{a}_{n+2}}{2}\text{for all}n\in \mathbb{N}$

[5.2.13] 

${({a}_{n})}_{n\ge 0}$ is geometric
$\iff {a}_{n}\cdot {a}_{n+2}\ge 0\wedge {a}_{n+1}=\sqrt{{a}_{n}\cdot {a}_{n+2}}\text{for all}n\in \mathbb{N}$

[5.2.14] 
Proof:
1. ►

"$\Rightarrow $": We employ the recursion formula ${a}_{n+1}={a}_{n}+d$ twice:
$\frac{{a}_{n}+{a}_{n+2}}{2}=\frac{{a}_{n}+{a}_{n+1}+d}{2}=\frac{{a}_{n}+d+{a}_{n+1}}{2}=\frac{{a}_{n+1}+{a}_{n+1}}{2}={a}_{n+1}$.
"$\Leftarrow $": We show by induction
${a}_{n+1}={a}_{n}+{a}_{1}{a}_{0}\text{for all}n\in \mathbb{N}$.
Thus ${({a}_{n})}_{n\ge 0}$ is represented as an arithmetic sequence with $c={a}_{0}\text{and}d={a}_{1}{a}_{0}\text{.}$
${0\in A}:{a}_{1}={a}_{0}+{a}_{1}{a}_{0}\text{.}$
${n\in A\Rightarrow n+1\in A}:$First we have from [5.2.13]: $2{a}_{n+1}={a}_{n}+{a}_{n+2}\text{.}$ This allows the following equation:
$\begin{array}{cc}\hfill {a}_{n+2}& =2{a}_{n+1}{a}_{n}\hfill \\ \hfill & =2{a}_{n}+2({a}_{1}{a}_{0}){a}_{n}\hfill \\ \hfill & =({a}_{n}+{a}_{1}{a}_{0})+{a}_{1}{a}_{0}\hfill \\ \hfill & ={a}_{n+1}+{a}_{1}{a}_{0}\text{.}\hfill \end{array}$

2. ►

"$\Rightarrow $": We proceed as we did in 1., also employing the recursion formula twice:
${a}_{n}\cdot {a}_{n+2}={a}_{n}\cdot {a}_{n+1}\cdot q={a}_{n}\cdot q\cdot {a}_{n+1}={a}_{n+1}\cdot {a}_{n+1}={a}_{n+1}^{\phantom{.}2}$.
As squares are positive we have ${a}_{n}\cdot {a}_{n+2}\ge 0$ as a first conclusion. The remainder of the assertion now follows when we extract the root.
"$\Leftarrow $": For the proof of this direction we have to consider two cases:

${a}_{1}=0$. Using ${a}_{n+1}=\sqrt{{a}_{n}\cdot {a}_{n+2}}$ we can show by induction: ${a}_{n}=0$ for all $n\ge 1$. Thus ${({a}_{n})}_{n\ge 0}={({a}_{0}\mathrm{,0,0,0,}\dots )}_{n\ge 0}$ is a geometric sequence with $q=0$.

${a}_{1}\ne 0$. Now an inductive argument gives: ${a}_{n}\ne 0\text{for all}n\in \mathbb{N}$. From this we show
$a}_{n+1}={a}_{n}\cdot \frac{{a}_{1}}{{a}_{0}}\text{for all}n\in \mathbb{N$,
just the same way we did in 1., so that ${({a}_{n})}_{n\ge 0}$ is a geometric sequence with $c={a}_{0}\wedge q=\frac{{a}_{1}}{{a}_{0}}\text{.}$
$0\in A}:{a}_{1}={a}_{0}\cdot \frac{{a}_{1}}{{a}_{0}}\text{.$
${n\in A\Rightarrow n+1\in A}:$From [5.2.14] we get: ${a}_{n+1}^{\phantom{.}2}={a}_{n}\cdot {a}_{n+2}\text{,}$ thus:
$\begin{array}{cc}\hfill {a}_{n+2}& =\frac{{a}_{n+1}^{\phantom{.}2}}{{a}_{n}}\hfill \\ \hfill & =\frac{{a}_{n+1}}{{a}_{n}}\cdot {a}_{n+1}\hfill \\ \hfill & =\frac{{a}_{n+1}}{{a}_{n}}\cdot {a}_{n}\cdot \frac{{a}_{1}}{{a}_{0}}\hfill \\ \hfill & ={a}_{n+1}\cdot \frac{{a}_{1}}{{a}_{0}}\text{.}\hfill \end{array}$


The next to last proposition touched an intersting, but often difficult problem: Does every recursive sequence allow a nonrecursive representation?
And if so, is there a general procedure for the transcription? It is very unlikely to find a solution for such a general problem, but from the arithmetic and geometric sequences we know
that single solutions are possible. So we have to study a given sequence individually to get an idea for a suitable formula. Whatever way a result was found,
the principle of induction is the standard tool for its verification.
Example: Let $({a}_{n})$ be the recursive sequence given by
$a}_{1}\u2254\frac{1}{2}\wedge {a}_{n+1}\u2254\frac{{a}_{n}+1}{2}\text{,$
i.e. $({a}_{n})=(\frac{1}{2},\frac{3}{4},\frac{7}{8},\frac{15}{16},\dots )$. It is quite obvious that the denominators represent the powers of 2 and that each numerator is one unit less the denominator.
Thus we have the idea:
$({a}_{n})=(\frac{{2}^{n}1}{{2}^{n}})$
Proof by induction:

The principle of recursion allows extensions in a varying manner. We could e.g. introduce two stage recursions:
We provide the first two sequence members ${a}_{1}$ und ${a}_{2}$ and thus can use two predecessors when calculating further members.
Example: The recursive sequence given by
${a}_{1}\u22541,{a}_{2}\u22541\wedge {a}_{n+2}\u2254{a}_{n+1}+{a}_{n}$

[5.2.15] 
is called Fibonacci sequence. Her members are calculated by adding the first two predecessors, so that the Fibonacci numbers start like this:
$\mathrm{1,1,2,3,5,8,13,21,34,55,}\dots $ .

Another option is to consider recursive sequences in ${\mathbb{R}}^{2}$.
Example: If the recursive sequence $(({a}_{n},{b}_{n}))$ is given by
$({a}_{1},{b}_{1})\u2254(2,1)\wedge ({a}_{n+1},{b}_{n+1})\u2254({a}_{n}+{b}_{n},{a}_{n}\cdot {b}_{n})\text{,}$
we get the following table of values: $(({a}_{n},{b}_{n}))=((\mathrm{2,1}),(\mathrm{3,2}),(\mathrm{5,6}),(\mathrm{11,30}),(\mathrm{41,330}),\dots )$
.
From the notation we see that a recursive sequence in ${\mathbb{R}}^{2}$ could be regarded as a coupled system of two recursive sequences in $\mathbb{R}$. So we could as well have said: Let $({a}_{n})$ and $({b}_{n})$ be given by
${a}_{1}\u22542,{b}_{1}\u22541\wedge {a}_{n+1}\u2254{a}_{n}+{b}_{n},{b}_{n+1}\u2254{a}_{n}\cdot {b}_{n}\text{.}$

For some years the theory of chaos gained a remarkable popularity, an absolute exception for a mathematical topic.
A final example in this part introduces a recursive sequence in ${\mathbb{R}}^{2}$ which is closely related with this popularity:
Example: For a fixed pair of numbers $({c}_{1},{c}_{2})\in \mathbb{R}$ we define the sequence $(({a}_{n},{b}_{n}))$ recursively by
$({a}_{1},{b}_{1})\u2254({c}_{1},{c}_{2})\wedge ({a}_{n+1},{b}_{n+1})\u2254({a}_{n}^{2}{b}_{n}^{2}+{c}_{1},2{a}_{n}{b}_{n}+{c}_{2})$

[5.2.16] 
We get different value tables for different values of $({c}_{1},{c}_{2})$. The following table shows three examples with the first sequence members and their distances $({a}_{n},{b}_{n})=\sqrt{{a}_{n}^{2}+{b}_{n}^{2}}$ to the point of origin as well.
$({c}_{1},{c}_{2})$ 
$({a}_{n},{b}_{n})$

$({a}_{n},{b}_{n})$ 



$(0,0)$

$(\mathrm{0,0}),(\mathrm{0,0}),(\mathrm{0,0}),(\mathrm{0,0}),(\mathrm{0,0}),\dots $

$\mathrm{0,0,0,0,0,}\dots $

$(0,1)$

$(\mathrm{0,1}),(\mathrm{1,1}),(\mathrm{0,}1),(\mathrm{1,1}),(\mathrm{0,}1),(\mathrm{1,1}),\dots $

$\mathrm{1,1.414,1,1.414,1,}\dots $

$(1,1)$

$(\mathrm{1,1}),(\mathrm{1,3}),(\mathrm{9,7}),(\mathrm{32,127}),\dots $

$\mathrm{1.414,3.162,11.4,130.97,}\dots $

Whereas some values of $({c}_{1},{c}_{2})$ produce steadily increasing distances, see e.g. the last example, there may be others where the distances are bounded.
If we mark all those initial values $({c}_{1},{c}_{2})$ in the plane where the distances do not exceed 2 we get an extraordinary subset of ${\mathbb{R}}^{2}$, the so called Mandelbrot set. Graphical editing of its margin reveals an amazing beauty:
The (mathematical) amazement is even greater if we blow up sections of the Mandelbrot set and blow up again and again.
It is rewarding to start a journey into the Mandelbrot set.
The Mandelbrot set is the most popular example of a so called fractal.
There are many more examples for fractals on the web. This site has a very exhaustive link list.
To produce fractals of your own you need information and tools.



