Mathematical Induction

When n = 1, 1(2)(3) = 6 = 2x3, which is divisible by 3
The proposition is true for n = 1.

Assume the proposition is true for n = k, i.e. k(k+1)(2k+1) is divisible by 3
Let k(k+1)(2k+1) = 3M, where M is any integer.
When n = k+1, (k+1)(k+2)(2k+2+1) = (k+1)(k+2)(2k+3)
= k(k+1)(2k+3)+2(k+1)(2k+3)
= [k(k+1)(2k+1) + 2k(k+1)]+2(k+1)(2k+3)
= 3M + 2(k+1)(k+2k+3)
= 3M + 6(k+1)^2
= 3(M+2(k+1)^2), which is divisible by 3
The proposition is true for n = k+1.
By M.I., the proposition is true for all natural numbers n

Let P(n) be the statement that,

n(n + 1)(2n + 1) is divisible by 3 for all natural numbers n

When n = 1

L.H.S. = 1 X 2 X 3 = 6 = 3 X 2, which is divisible by 3

So, P(1) is true.


Assume P(n) is true for n = k

k(k + 1)(2k + 1) = 3N, where N is an integer

2k^3 + 3k^2 + k = 3N


When n = k + 1

(k + 1)(k + 2)[2(k + 1) + 1]

= (k + 1)(k + 2)(2k + 3)

= k(2k^2 + 7k + 6) + (2k^2 + 7k + 6)

= 2k^2 + 9k^2 + 13k + 6

= (2k^2 + 3k^2 + k) + 6k^2 + 12k + 6

= 3N + 3(2k^2 + 4k + 2)

= 3(N + 2k^2 + 4k + 2), which is also divisible by 3

So, by the principle of M.I., P(n) is true for all natural numbers n