# MA375: The Principle of Induction

Lecture Notes

Example: Prove that $\forall n\in{\mathbb N}, n^5-n$ is a multiple of n.

Base case: n=0... $0^5=0$ as we want

Inductive step: Assume that 5 divides $n^5-n$ and show that 5 divides $(n+1)^5-(n+1)$

P(1) = 1-1 = 0 (true,divisible by 5)

P(2) = 32-2 = 30 (true,divisible by 5)

let P(m) be true, P(m+1) = $(m+1)^5-m$

P(m+1) = $(m^5+1)+5*(other terms)$.

which is divisible by 5 since P(m) is true.

Hence 5| $n^5-n$

## Alumni Liaison

To all math majors: "Mathematics is a wonderfully rich subject."

Dr. Paul Garrett