Mathematical Induction

Purpose

Used to prove properties for sequences (e.g. natural numbers)

Closed Form of Sequence

Closed form formula represents a sequence. It shows how the value of sequence term $a_k$ depends on $k$, e.g. $a_k=2k$ for all integers $k\ge 1$

Sequence Comprehension

Sequences can be represented: $a=[2k:k\in [\mathrm{1..}]]$
Type signature: $Seq(Q)=([1,\infty )\to Q)$

Recurrence Relation

A formula that relates each term $a_k$ to some of its predecessors
e.g. factorial:
0! = 1 n! = n (n-1)! for n $\ge$ 1

Recursive definition of set

For a set $S$,

• base clause: Specify that certain elements, called founders are in $S$
• recursion clause: Specify certain functions, called constructors, under which set $S$ is closed: if $f$ is a constructor and $x\in S$ , then $f(x)\in S$
• minimiality clause: Membership for $S$ can always be demonstrated by finitely many successive applications of the clauses above

Principle of MI (1PI)

Let $P(n)$ be a property that is defined for integers $n$ and let $a$ be a fixed integer. Suppose the following statements are true:

1. $P(a)$ is true.
2. For all integers $k\ge a$ , if $P(k)$ is true then $P(k+1)$ is true.
   Then the statement “for all integers $n\ge a,P(n)$” is true.

Formally

$P(a)$ $\forall k\ge a,P(k)\Rightarrow P(k+1)$ $\therefore \forall k\ge a,P(k)$

To use

To prove “Fol all integers $n\ge a$ , a property $P(n)$ is true”
Step 1 (basis step): Show that $P(a)$ is true
Step 2 (inductive step): Show that for all integers $k\ge a$ , if $P(k)$ is true, then $P(k+1)$ is true, by the following:
Suppose that $P(k)$ is true, where $k$ is any particular but arbitrarilty chosen integer with $k\ge a$ (This is called the inductive hypothesis)
Then, show that $P(k+1)$ is true.

Example

Prove that for all integers $n\le 3,2n+1<2^n$

1. Let $P(n)\equiv (2n+1<2^n),\forall n\in {\mathbb{Z}}_{\ge 3}$
2. Basis step: $2\cdot 3+1=7<8=2^3$ . Therefore, $P(3)$ is true.
3. Assume $P(k)$ is true for $k\ge 3$ . That is, $2k+1<2^k$
4. Inductive step: (to show P(k+1) is true) 4.1. $2(k+1)+1=2k+3=(2k+1)+2<2^k+2<2^k+2^k=2^{k+1}$ (because $2<2^k$ for all integers $k\ge 2$ ) 4.2. Therefore $P(k+1)$ is true
5. Therefore, $P(n)$ is true for all integers $n\ge 3$

Principle of Strong MI (2PI)

Let $P(n)$ be a property that is defined for integers $n$ and let $a$ and $b$ be fixed integers with $a\le b$ . Suppose these statements are true:

1. $P(a),P(a+1),\dots ,P(b)$ are all true (basis step)
2. For any integer $k\ge b$ , if $P(i)$ is true for all integers $i$ from $a$ through $k$ , then $P(k+1)$ is true ($P(a)\wedge P(a+1)\wedge \dots \wedge P(k)\Rightarrow P(k+1)$ ) (inductive step)
   Then the statement “for all integers $n\ge a,P(n)$ ” is true

Variation 1

If

1. $P(a),P(a+1),\dots ,P(b)$ hold
2. For every $k\ge a,P(k)\Rightarrow P(k+b-a+1)$ ($P(k)$ implies something further down)
   Then $P(n)$ holds for all $n\ge a$

Variation 2

If

1. $P(a),P(a+1),\dots ,P(b)$ hold
2. For every $k\ge b\exists ia\le i\le k,P(i)\Rightarrow P(k+1)$ ($P(i)$, where $a\le i\le k$ implies $P(k+1)$)
   Then $P(n)$ holds for all $n\ge a$

Example

Prove that any whole amount \geq \12$canbeformedbyacombinationof$4 and $5 coins

1. Let $P(n)\equiv (n=4a+5b)$ , for some $a,b\in \mathbb{N},n\ge 12$
2. Basis step: Show that $P(12),P(13),P(14),P(15)$ hold: $12=4\cdot 3+5\cdot 0;13=4\cdot 2+5\cdot 1;$ (etc. not written here)
3. Assume $P(i)$ holds for $12\le i\le k$ given some $k\ge 15$
4. Inductive step: (To show $P(k+1)$ is true) 4.1. $P(k-3)$ holds (by induction hypothesis), so $k-3=4a+5b$ for some $a,b\in \mathbb{N}$ 4.2. $k+1=(k-3)+4=(4a+5b)+4=4(a+1)+5b$ 4.3. Hence, $P(k+1)$ is true
5. Therefore, $P(n)$ is true for $n\ge 12$