5. Induction

5.1 Sequences

Sequence: a special type of function in which the domain is a set of consecutive integers
Term of a sequence: a value of $g_k$
Index of $g_k$: $k$
Entire sequence: $\{g_k\}$

The sequence may start with any integer

Finite sequence: a sequence with finite domian
A finite sequence has an initial index $m$ and a final index $n$, where $n\ge m$
$a_m$ is the initial term and $a_n$ is the final term

Infinite sequence: a sequence with an infite domain
There is an initial index $m$ and the sequence is defined for all indices $k$ such that $k\ge m$

Explicit formula: showing how the value of term $a_k$ depends on $k$

Increasing: for every two consecutive indices, $k$ and $k+1$, in the domain, $a_k<a_{k+1}$
Nondecreasing: $a_k\le a_{k+1}$
Decreasing: $a_k>a_{k+1}$
Nonincreasing: $a_k\ge a_{k+1}$

Geometric sequence: a sequence of real numbers where each term after the initial term is found by taking the previous term and multiplying by a fixed number called common ratio
$s_k=a{r}^k$, $k\ge 0$, $k\in \mathbb{Z}$

Arithmetic sequence: a sequence of real numbers where each term after the initial term is found by taking the previous term and adding a fixed number called the common difference
$t_n=t_0+dn$, $n\ge 0$, $n\in \mathbb{Z}$

5.2 Summations

Summation notation: used to express the sum of terms in a numerical sequence
Index: in the summation ${\sum }_{i=s}^t{a}_i$, the variable $i$
Lower limit: $s$
Upper limit: $t$

Summation form: ${\sum }_{j=1}^4{j}^3$
Expanded form: $1^3+2^3+3^3+4^3$

Closed form: a mathematical expression that expresses the value of the sum without summation notation
${\sum }_{k=0}^{n-1}(a+kd)=an+\frac{d(n-1)n}{2}$, $n\in \mathbb{Z}$, $n\ge 1$
${\sum }_{k=0}^{n-1}a\cdot r^k=\frac{a(r^n-1)}{r-1}$, $r\in \mathbb{R}$, $r\ne 1$, $n\in \mathbb{Z}$, $n\ge 1$

5.3 Mathematical induction

Base case: establishes that the theorem is true for the first value in the sequence
Inductive step: establishes that if the theorem is true for $k$, then the theorem also holds for $k+1$

PMI: if the base case $P(n_0)$ is true and $P(k)$ being true implies that $P(k+1)$ is true for every integer $k\ge n_0$, then $P(n)$ holds for all integers $n\ge n_0$
Inductive hypothesis: the supposition that $P(k)$ is true

5.4 More inductive proofs

Recurrence realtions

5.5 Strong induction and well-ordering

Principle of strong induction: the fact to be proven holds for all values less than or equal to $k$

In strong induction, the base case proves $S(n)$ for all $a\le n\le b$, and the inductive step assumes $S(j)$ holds for all $a\le j\le k$, where $k\ge b$, to prove $S(k+1)$

Well-ordering principle: any nonempty subset of nonnegative integers has a smallest element

Proof: Well-Ordering Implies Mathematical Induction

1. Assume $\neg P(n)$ for some $n\ge 1$.
2. Let $S=\{n\in \mathbb{Z}\mid n\ge 1\wedge \neg P(n)\}$.
3. By the well-ordering principle, $S$ has a smallest element $m$.
4. Case 1: If $m=1$, then $\neg P(1)$, so the base case fails.
5. Case 2: If $m\ge 2$, then $P(m-1)$ is true but $P(m)$ is false. Let $k=m-1$. Thus $P(k)$ is true but $\neg P(k+1)$, so the inductive step fails.
6. Therefore, if $P(n)$ is false for some $n\ge 1$, either the base case or inductive step fails. By contraposition, mathematical induction holds.

Proof by Well-Ordering Principle:

1. Assume $\neg P(n)$ for some $n\ge b$.
2. Let $S=\{n\in \mathbb{Z}\mid n\ge b\wedge \neg P(n)\}$.
3. By the well-ordering principle, $S$ has a smallest element $m$.
4. Show that there exists $k\in S$ with $k<m$, contradicting the minimality of $m$.
5. Therefore, $S=\varnothing$, and $\forall n\ge b,P(n)$.

---

TEMPLATE:
Proof
By induction on $n$

Base case: $n=n_0$
Show that $P(n_0)$ is true (LHS = RHS)

Inductive step:
Suppose $P(k)$ is true for some integer $k\ge n_0$ (Inductive Hypothesis).
We will show that $P(k+1)$ is also true
Proof using the inductive hypothesis

Therefore, by PMI, $P(n)$ holds for all integers $n\ge n_0$. $QED$