Induction

## Mathematical induction
            ---
            ## Proof by induction
            Useful for proving a statement about all positive integers.

eg: For all $n\in\mathbb{N}$, the last digit of $5^n$ is $5$.

Comprised of:
 * Base case: Statement is true for number $1$. 
 eg: $5^1=5$, whose last digit is $5$.
 * Inductive Step: If statement is true number $n$, then it is true for number $n+1$. 
 eg: if $5^n=10a+5$ for some $a\in\mathbb{Z}$, then $5^{n+1} = 5(10a+5)=50a+25=10(5a+2)+5$, whose last digit is $5$.
 * Conclusion: "Hence, by induction, [statement] is true for all $n\in\mathbb{N}$."
 ---
 ## Example 2 of induction
 #### Theorem
 For all $n\in\mathbb{N}$, $5^{2n}-1$ is a multiple of $3$.
 #### Proof: Base case
 $5^{2\times1}-1 = 25-1 = 24 = 3\times8$, which is divisible by $3$.
 
 ---
 ## Example 2 of induction
 #### Theorem
 For all $n\in\mathbb{N}$, $5^{2n}-1$ is a multiple of $3$.
 #### Proof: Inductive step
 Suppose that, for some particular $n\in\mathbb{N}$, $5^{2n}-1$ is a multiple of $3$.

Then $\exists c\in\mathbb{Z}:5^{2n}-1 = 3c$.

Therefore, $5^{2(n+1)}-1 = 25 (5^{2n}) - 1 = 25 (5^{2n}-1) + 25 - 1 = 25(3c) + 24 = 3(25c) + 3(8)$, which is also divisible by $3$.
 
 ---
 ## Example 2 of induction
 #### Theorem
 For all $n\in\mathbb{N}$, $5^{2n}-1$ is a multiple of $3$.
 #### Proof: Conclusion
 Hence, by induction, $5^{2n}-1$ is a multiple of $3$ is true for every $n\in\mathbb N$.
 
 ---
 ## Anatomy of an inductive proof: eg. 2
 #### Theorem $Q(n)$$Q(n)$$Q(n)$of form $\forall n \in\mathbb N$  $Q(n)$
 For all $n\in\mathbb{N}$,
 $5^{2n}-1$ is a multiple of $3$$5^{2n}-1$ is a multiple of $3$$5^{2n}-1$ is a multiple of $3$$5^{2n}-1$ is a multiple of $3$.
 #### Proof: Base case $Q(1)$$Q(1)$$Q(1)$of form $Q(1)$
 $5^{2\times1}-1$$5^{2\times1}-1$$5^{2\times1}-1$$5^{2\times1}-1$
 $= 25-1 = 24 = 3\times8$, which
 is divisible by $3$is divisible by $3$is divisible by $3$is divisible by $3$.
 #### Proof: Inductive step $Q(n)$$Q(n)$$Q(n)$of form $Q(n)$$\implies$$Q(n+1)$
 Suppose that, for some particular $n\in\mathbb{N}$,
 $5^{2n}-1$ is a multiple of $3$$5^{2n}-1$ is a multiple of $3$$5^{2n}-1$ is a multiple of $3$$5^{2n}-1$ is a multiple of $3$.

Then $\exists c\in\mathbb{Z}:5^{2n}-1 = 3c$.

Therefore,
 $5^{2(n+1)}-1$$5^{2(n+1)}-1$$5^{2(n+1)}-1$$5^{2(n+1)}-1$
 $ = 25 (5^{2n}) - 1 = 25 (5^{2n}-1) + 25 - 1 = 25(3c) + 24 = 3(25c) + 3(8)$, which
 isisisis
 also
 divisible by $3$divisible by $3$divisible by $3$divisible by $3$.
 #### Proof: Conclusion $Q(n)$$Q(n)$$Q(n)$of form Hence, by induction, $\forall n \in\mathbb N$,  $Q(n)$
 Hence, by induction,
 $5^{2n}-1$ is a multiple of $3$$5^{2n}-1$ is a multiple of $3$$5^{2n}-1$ is a multiple of $3$$5^{2n}-1$ is a multiple of $3$
 is true for every $n\in\mathbb N$.
 
 ---
 ## Anatomy of an inductive proof: eg. 1
 #### Theorem $Q(n)$$Q(n)$$Q(n)$of form $\forall n \in\mathbb N$  $Q(n)$
 For all $n\in\mathbb{N}$, the last digit of $5^n$ is $5$the last digit of $5^n$ is $5$the last digit of $5^n$ is $5$the last digit of $5^n$ is $5$.
 #### Proof: Base case $Q(1)$$Q(1)$$Q(1)$of form $Q(1)$
 $5^1$$5^1$$5^1$$5^1$$=5$,
 whose last digit is $5$whose last digit is $5$whose last digit is $5$whose last digit is $5$.

#### Proof: Inductive step $Q(n)$$Q(n)$$Q(n)$of form $Q(n)$$\implies$$Q(n+1)$
 If $5^n=10a+5$ for some $a\in\mathbb{Z}$$5^n=10a+5$ for some $a\in\mathbb{Z}$$5^n=10a+5$ for some $a\in\mathbb{Z}$$5^n=10a+5$ for some $a\in\mathbb{Z}$,
 then $5^{n+1}$$5^{n+1}$$5^{n+1}$$5^{n+1}$
 $= 5(10a+5)=50a+25=10(5a+2)+5$
 whose last digit is $5$whose last digit is $5$whose last digit is $5$whose last digit is $5$.

#### Proof: Conclusion $Q(n)$$Q(n)$$Q(n)$of form Hence, by induction, $\forall n \in\mathbb N$,  $Q(n)$
 Hence, by induction, $5^{n}$ is divisible by $5$$5^{n}$ is divisible by $5$$5^{n}$ is divisible by $5$$5^{n}$ is divisible by $5$ is true for every $n\in\mathbb N$.
 
 ---
 ## Anatomy of an inductive proof: demonstration
 #### Theorem
 of form $\forall n \in\mathbb N$,  $Q(n)$
 #### Proof: Base case
 of form $Q(1)$
 #### Proof: Inductive step
 of form $Q(n)\implies Q(n+1)$
 #### Proof: Conclusion
 Hence, by induction, $\forall n \in\mathbb N$,  $Q(n)$
 
 ---
 ## Anatomy of an inductive proof: demonstration
 #### Theorem
 of form $\forall n \in\mathbb N$  such that $n\geqslant3$,  $Q(n)$
 #### Proof: Base case
 of form $Q(3)$
 #### Proof: Inductive step
 of form $Q(n)\implies Q(n+1)$
 #### Proof: Conclusion
 Hence, by induction, $\forall n \in\mathbb N$  such that $n\geqslant3$,  $Q(n)$