Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

closed as off-topic by azimut, Daniel Rust, Davide Giraudo, Stefan Hamcke, Dennis Gulko Oct 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, Daniel Rust, Davide Giraudo, Stefan Hamcke
If this question can be reworded to fit the rules in the help center, please edit the question.

2  
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$ –  Ahmed Oct 17 '13 at 19:50

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

$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

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.