Prove by induction that for all natural numbers, n, either 3|n or 3|n+1 or 3|n+2?

Question

That is prove that for all natural numbers, n, either 3 is a factor of n or n+1 or n+2

Hint: every $t \in N$ can be written as $t=3x+q$ – SomeOne Oct 17 '13 at 19:50 — SomeOne, Oct 17 '13 at 19:50

score 2 · Accepted Answer · answered Oct 17 '13 at 19:49

Base case: n = 1.

Then 3 divides 3, which is n+2.

Inductive hypothesis: if the proposition is true for n: Then proof by cases

1). If n is divisible by 3, this implies that (n+1) + 2 is also divisible by 3.

2). If n +1 is divisible by 3, then (n+1) is also divisible by 3.

3). If n+2 is divisible by 3, then (n+1) + 1 is also divisible by 3.

Thus, for all natural numbers ,n, the 3 divides either n, n+1, or n+2.

score 0 · Answer 2 · answered Oct 17 '13 at 20:00

(Base case: n=1): 3 is a factor of 3 = n+2.

Inductive step.

Assume that 3 is a factor of k.

Then there exists an integer p such that $k = 3p.$

This means that $(k+1)+2 =k+3 = 3(p+1)$ and so 3 is a factor of (k+1) + 2.

The result follows by induction.

score 0 · Answer 3 · answered Oct 17 '13 at 20:01

Here is another hint for a different way of doing the induction step.

For $n$ the three numbers are $n, n+1, n+2$

For $n+1$ the three numbers are $n+1, n+2, n+3$

Consider two cases - that one of the common numbers is divisible by $3$ (easy); or ... (you fill in the gap).

score 0 · Answer 4 · answered Oct 17 '13 at 20:03

$P(n) = 3 | (n + 0) \lor 3 | (n + 1) \lor 3 | (n + 2) \tag {to prove}$

$P(0)$ is true trivially. Now we must establish $P(n) \rightarrow P(n + 1)$

Assume: $3 | (n + 0) \lor 3 | (n + 1) \lor 3 | (n + 2) \tag {inductive hypothesis}$

Establish: $3 | (n + 1) \lor 3 | (n + 2) \lor 3 | (n + 3) \tag {inductive result}$

4 Answers4