Question

Use the Principle of Mathematical Induction to prove that 2 | (n2 − n) for all n ≥ 0.

Answer 1

or
prove that (n^2 − n) is divisible by 2 for all n ≥ 0

1. test if true for n = 1
1-1 = 0 , I guess that is true
2. assume that it is true for n = k, that is : k^2 - k is divisible by 2
3. show that it must be true for n = k+1
using the fact that if two numbers are divisible by some value of m then their
difference is also divisible by m

take the difference (k+1)^2 - (k+1) - (k^2 - k)
= k^2 + 2k + 1 - k - 1 - k^2 + k
= 2k, which is even, thus divisible by 2
Q.E.D.

Of course we could have just noticed that n^2 + n
= n(n+1), which would be 2 consecutive natural numbers
if n is even, then n+1 is odd
if n is odd, then n+1 is even, and the product of an odd times an even is always even