UNO High School Problem of the Week Competition

News

About

Prizes

Problems & Solutions

Scores

Archive

Links

Problem 5


Using mathematical induction, prove that n3 + 2n is a multiple of 3 for all positive integers n.


Solution

Step 1: Show that the statement holds true for n = 1.

(1)3 + 2(1) = 3
Thus the statement holds true for n = 1.

Step 2: Let k be an arbitrary positive integer greater than 1, and assume that the statement holds true for k.

That is, assume that k3 + 2k is divisible by 3.

Step 3: Show that the statement holds true for k+1.

(k+1)3 + 2(k+1)
= k3 + 2k2 + k + k2 + 2k + 1 + 2k + 2.
By simplifying and rearranging,
= (k3 + 2k) + 3(k2 + k + 1)
By the induction hypothesis,(k3 + 2k) is divisible by 3 and can be written as 3m, where m is a positive integer.
= 3m + 3(k2 + k + 1)
= 3(m + (k2 + k + 1))
Since 3(m + (k2 + k + 1)) is a multiple of 3, 3 divides it.
Thus the statement holds true for k+1 and is true for all positive integers n.