rWa37

Discrete Mathematics Lecture 8 — Induction and Recursion

University course in discrete mathematics for computer science and engineering.

Sep 28, 2021
Downloads ‐ HTML, Markdown, PDF
All Files ‐ Post Files

Continuing from the last example…

Prove that \(n^2<2^n \forall n \geq 5\).

It is ok for \(n=0\) and \(n=1\), but not for \(n=2, 3, 4\). But then it is ok for \(n \geq 5\).

So the proof must take into account that \(n \geq 5\), otherwise it would not be correct.

So we can go ahead and prove by induction.

Step 1: Control the base case, \(n=5\).

\[ 5^2<2^5 \]

which is true.

Step 2: Assume that

\[ n^2<2^n \tag{1} \]

We want to derive that

\[ (n+1)^2 < 2^{n+1} \tag{2} \]

without forgetting that

\[ n \geq 5 \tag{3} \]

We can take the left side of (2)

\[ \begin{aligned} (n+1)^2 &= n^2 + 2n + 1 \\ & \stackrel{(3)}{<} n^2 + 2n + n \\ &= n^2 + 3n \\ & \stackrel{(3)}{<} n^2 + n^2 \\ & = 2n^2 \\ & \stackrel{(1)}{<} 2(2^n) \\ &= 2^{n+1} = \text{Right hand of (2)} \end{aligned} \]

Recursion

We will focus on recursively defined number series.

Ex.1: We have already seen that the set of subsets in a n-element set, is \(2^n\) (multiplication principle).

For every \(n \in \mathbb{N}\), let \(a_n = \text{ the amount of subsets to } \{1, 2, ..., n \}\), (\(n=0\) is \(\{\}\)).

We state that the following so called recursive formula is true for the series

\[ a_0, a_1, a_2, ... = \left ( a_n \right )_{n=0}^{\infty} \]

\[ a_0 = 1 \text{ (base case)} \]

\[ a_{n+1} = 2a_n \forall n \geq 0 \text{ (recursive formula)} \]

Step 1: Control the base case.

\[ \{\}, a_0 = 1 \]

Step 2: Verify the recursive formula.

The formula says that if you add one element to the set, then the amount of subsets double.

This is true because for every previous subset you had, you have the option to add or not add the new element to them. Therefore doubleing the possible amount of subsets.

Every subset to \(\{1, 2, ... n\}\) give possibility of two subsets \(\{1, 2, ..., n+1\}\), or not to add \(n+1\).

Now there only remains to prove that \(a_n=2^n \forall n \geq 0\). You would do this with induction.

Step 1: Control the base case \(n=0\).

\[ a_0=1=2^0 \]

ok

Step 2: Assume that the formula is valid for

\[ a_n = 2^n \tag{1} \]

\[ a_{n+1}=2^{n+1} \tag{2} \]

We know

\[ \begin{aligned} a_{n+1} &= 2a_n \\ & \stackrel{(1)}{=} 2(2^n) \\ &= 2^{n+1} \end{aligned} \]

end of proof

Ex.2: Prove a recursive formula and then a “explicit” formula for the following number series.

\[ 0, 1, 4, 13, 40, 121, ... \]

\[ \begin{aligned} a_0 &= 0 \\ a_{n} &= 3a_{a-1}+1 \forall n \geq 1 \\ \Leftrightarrow a_{n+1} &= 3a_n + 1 \forall n \geq 0 \end{aligned} \]

Explicit Formula: \(a_n = \frac{3^n-1}{2} \forall n \geq 0\).

Note: This is an example of a so called linear recursion. For which there exists a general procedure in order to get a explicit formula for the recursion (this is beyond this class).

Although you could be asked if a given explicit formula is correct.

We verify the formula with a induction proof.

Step 1: Verify the base case, \(n=0\).

\[ a_0 = 0 = \frac{3^0-1}{2} = \frac{1-1}{2} = 0 \]

which is correct.

Step 2: Assume that

\[ a_n = \frac{3^n-1}{2} \tag{1} \]

and we want to derive that

\[ a_{n+1}=\frac{3^{n+1}-1}{2} \tag{2} \]

All we know is that \(a_{n+1}=3a_n+1\).

\[ \begin{aligned} a_{n+1} &= 3a_n+1 \\ & \stackrel{(1)}{=} 3 \left ( \frac{3^n - 1}{2} \right ) + 1 \\ &= \frac{(3^{n+1}-3)+2}{2}=\frac{3^{n+1}-1}{2} \end{aligned} \]

end of proof

Extended Induction Principle

(more than one base case)

Ex.3: Let \((a_n)_{n=0}^{\infty}\) be the number series which is defined recursively according to

\[ a_0=1, a_1=4, a_n=5a_{n-1}-6a_{n-2} \forall n \geq 0 \]

  1. Calculate \(a_2, a_3\)
  2. Prove that \(a_n=2\cdot 3^n - 2^n \forall n \geq 0\)

So for excerise 1.

\[ \begin{aligned} a_2 = 5a_1 - 6a_0 = 5(4)-6(1) &= 14 \\ a_3 = 5a_2-6a_1=5(14)-6(4) &= 46 \end{aligned} \]

And for excersize 2 we do a proof by induction according to the following principle.

We have a predicate \(P(n)\) which we will prove is true \(\forall n \geq 0\).

  • Step 1: Verify \(P(0), P(1)\).
  • Step 2: Show that \(P(n) \land P(n+1) \Rightarrow P(n+2)\).

Now trying this new principle…

Step 1: Verify the base cases, \(n=0, n=1\).

  • \(n=0, a_0=1\)
    • \(2 \cdot 3^0 - 2^0 = 2 \cdot 1 - 1 = 1\), is true.
  • \(n=1, a_1=4\)
    • \(2 \cdot 3^1 - 2^1 = 2 \cdot 3 - 2 = 4\), is true.

Step 2: Induction step. Assume that

\[ a_n = 2 \cdot 3^n-2^n \tag{1} \]

and

\[ a_{n+1} = 2 \cdot 3^{n+1} - 2^{n+1} \tag{2} \]

Derive that

\[ a_{n+2} = 2 \cdot 3^{n+2} - 2^{n+2} \tag{3} \]

We know that

\[ a_{n+2} = 5 a_{n+1} - 6a_n \]

\[ \begin{aligned} a_{n+2} &= 5 a_{n+1} - 6a_n \\ &\stackrel{(1), (2)}{=} 5 \left( 2 \cdot 3^{n+1} - 2^{n+1} \right) - 6 \left ( 2 \cdot 3^n - 2^n \right ) \\ &= 3^n ( 5 \cdot 2 \cdot 3 - 6 \cdot 2) - 2^n(5 \cdot 2 - 6) \\ &= 18 \cdot 3^n - 4 \cdot 2^n \\ &= 2 \cdot (9 \cdot 3^n) - 2^2 \cdot 2^2 = 2 \cdot 3^{n+2} - 2^{n+2} \end{aligned} \]

end of proof

Extended Induction Principe with \(k\) base cases (\(k \geq 1\))

You want to prove that a predicate \(P(n)\) is true for all \(n \geq n_0\).

Step 1: Verify

\[ P(n_0), P(n_0 + 1), ..., P(n_0 + k - 1) \]

Step 2: Prove that the \(k\) previous cases implicates the next case.

\[ P(n) \land P(n_1) \land ... \land P(n+k-1) \Rightarrow P(n+k) \]

Example where you must first reason to get the recursion formula:

For \(n \geq 0\), let \(a_n\) be the number of n-digit binary word, without adjecent zeroes.

  • \(n=0, a_0 = 1\)
  • \(n=1, a_1 = 2\)
    • 0
    • 1
  • \(n=2, a_2=3\)
    • 01
    • 10
    • 11
  • \(n=3, a_3=5\)
    • 000
    • 001
    • 010
    • 100
    • 011
    • 101
    • 110
    • 111
  • \(n=4, a_4=8\)

It seems that the following is the pattern.

\[ \begin{aligned} & a_n = a_{n-1}+a_{n-2} \forall n \geq 2 \\ & a_0=1, a_1=2 \end{aligned} \]

Proof:

Step 1: Verify the base cases \(a_0=1, a_1=2\).

Step 2: To explain the recursive formula requires its own so called combinatoric reasoning.

Take an n-digit binary number. Then you have two choices for the first digit: 0 or 1.

Case 1: First digit is 1.

So

\[ 1\boxed{\text{other digits}} \]

In this case the number is ok if and only if the remaining \(n-1\) digits make up a ok number \(\Rightarrow a_{n-1}\) possible numbers.

Case 2: The first digit is a 0.

\[ 0\boxed{\text{other digits}} \]

In this case the number is ok if and only if the second digit is a 1. The number is now ok if and only if the remaining \(n-2\) digits make up a valid number \(\Rightarrow a_{n-2}\) possible numbers.

In total you would have \(a_{n-1}+a_{n-2}\) valid n-digit numbers \(\Rightarrow a_n = a_{n-1}+a_{n-2}\).

Fibonacci Numbers

\[ \begin{aligned} f_0 &= 1 \\ f_1 &= 1 \\ \end{aligned} \]

\[ f_n = f_{n-1}+f_{n-2} \forall n \geq 2 \]

\(f_n\) 1 1 2 3 5 8
\(a_n\) 1 2 3 5 8

\[ \Rightarrow a_n = f_{n+1} \]

Explicit Formula:

\[ f_n = \frac{1}{\sqrt{5}} \left ( \left ( \frac{1 + \sqrt{5}}{2} \right ) ^ { n + 1 } - \left ( \frac{1 - \sqrt{5}}{2} \right ) ^ {n + 1} \right ) \]

The method for how to derive this explicit formula is beyond this course but the general idea will be given.

The formula should be a exponential function, that is to say.

\[ f_n = c^n \]

You would plug it in and

\[ \begin{aligned} f_n = f_{n-1}+f_{n-2} &\Rightarrow c^n = c^{n-1} + c^{n-2} \\ &\Rightarrow c^2 = c + 1 \\ &\Rightarrow c^2-c-1 = 0 \\ &\Rightarrow c = \frac{1 \pm \sqrt{5}}{2} \quad c_1, c_2 \end{aligned} \]

Clause:

\[ f_n = A \cdot c_1^n + B \cdot c_2^n \]

where \(A, B\) are determined of the initial values \(f_0, f_1\) (linear algebra).

In the explicit formula for the fibonacci numbers, the

\[ \left ( \frac{1 - \sqrt{5}}{2} \right ) ^ {n+1} \]

will go to zero as you grow to infinity. The

\[ \left ( \frac{1 + \sqrt{5}}{2} \right ) ^ {n + 1} \]

term will be the most prominent term.

where

\[ \frac{1 + \sqrt{5}}{2} \]

is called the Golden Section.

References