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

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

-

## closed as off-topic by azimut, Dan Rust, Davide Giraudo, Stefan Hamcke, Dennis GulkoOct 17 '13 at 21:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – azimut, Dan Rust, Davide Giraudo, Stefan Hamcke
If this question can be reworded to fit the rules in the help center, please edit the question.

What have you tried? (The tag on your question seems to be a helpful hint). – Henning Makholm Oct 17 '13 at 19:45
Hint: every $t \in N$ can be written as $t=3x+q$ – SomeOne Oct 17 '13 at 19:50

## 4 Answers

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.

-

(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.

-

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).

-

$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}$

Break the inductive assumption into cases:
if $3|(n + 0)$ then $3|(n + 3)$, inductive result follows
if $3|(n + 1)$ then $3|(n + 1)$, inductive result follows
if $3|(n + 2)$ then $3|(n + 2)$, inductive result follows

-