# 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 $