Mathematical Induction: Number Theory

Mathematical Induction is used to prove that the statement of the problem is true for all natural numbers $n$. Mathematical Induction consists of proving the following three theorems.

Theorem 1 (Base of Induction): The statement of the problem is true for $n = 1$.

Theorem 2 (Inductive Step): If the statement is true for some $n = k$, then it must also be true for $n = k + 1$.

Theorem 3 (Peano Axiom): If Theorems 1 and 2 hold, then the statement of the problem is true for all natural numbers $n$.

Problem (Moscow City, 1961)

Let $F_{m}$ be the $m$-th term of a Fibonacci sequence defined as $F_1=1$, $F_2=1$, $F_{m+2}=F_{m+1}+F_{m}$ for $m \in \mathbb{N}$. Show that $F_{5n} $ is divisible by $5$ for all $n \in \mathbb{N}$ .

Solution

Theorem 1 (Base of Induction): The statement is true for $n = 1$: $F_5=5$ is divisible by $5$.

 

Theorem 2 (Inductive Step): Let us assume that the statement holds for $n = k$, i.e. for some $x \in \mathbb{N} $

$$ F_{5k} = 5x $$

Let $F_{5k+1} = y$. Then we have

$ F_{5k+2} = F_{5k+1} + F_{5k} = 5x+y $

$ F_{5k+3} = F_{5k+2} + F_{5k+1} = 5x+2y $

$ F_{5k+4} = F_{5k+3} + F_{5k+2} = 10x+3y $

$ F_{5k+5} = F_{5k+4} + F_{5k+3} = 15x+5y $

and therefore $ F_{5k+5}$ is also divisible by $5$ and therefore the statement holds for $n=k+1$.

Theorem 3 (Peano Axiom): Since the Theorems 1 and 2 hold, then the statement of the problem is true for all $n \in \mathbb{N}$.

---