Proof by Induction

Proof by Induction

To Prove: f(n) = n(n+1)(2n+1) is divisible by 6 for all natural numbers n ≥ 1

Base Case: n=1
f(1) = 1 *2 * 3 = 6
which clearly divides by 6, so the statement holds for n = 1

Assumption: n=k
Assume that for some natural number k, that f(k) = k(k+1)(2k+1) = 2k3+3k2+k is divisible by 6.

Inductive Step: n=k+1: If it is true for n=k, show it is true for n=k+1.
f(k+1) = (k+1)(k+2)(2(k+1)+1)
= 2k3 +9k2 +13k +6
= (2k3+3k2+k) + (6k2 +12k +6)
= (2k3+3k2+k) + 6(k2+2k+1)

Since “6(k2+2k+1)” is clearly divisible by 6, and we assumed that (2k3+3k2+k) is, then (2k3+3k2+k) + 6(k2+2k+1) must be divisible by 6 too.


Given that the statement is true for n=1, and having shown that if it is true for n=k, it is also true for n=k+1, so by induction, f(n) is divisible by 6 for all n N.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s