Hi the problem is:

Prove that 6 is a factor of n^3+3n^2+2n for all natural numbers n.

I don't know where to start with these kinds of problems, can anyone help?

THANKS SO MUCH.

Printable View

- Nov 22nd 2008, 11:41 AMxoluosoxMathematical induction
Hi the problem is:

Prove that 6 is a factor of n^3+3n^2+2n for all natural numbers n.

I don't know where to start with these kinds of problems, can anyone help?

THANKS SO MUCH. - Nov 22nd 2008, 11:58 AMMathstud28
Ok so our hypothesis is that $\displaystyle n^3+3n^2+2n=n(n+1)(n+2)|6~\forall{n}\in\mathbb{N}$

So lets begin

Base Step: $\displaystyle n=1$

When $\displaystyle n=1$ we have $\displaystyle (1)(1+2)(1+3)=6|6$

So that is true

Restate the hypothesis: $\displaystyle \forall{n}\in\mathbb{N}~n(n+1)(n+2)|6$

Inductive step: Now we have to just using the hypothesis prove that

$\displaystyle (n+1)(n+2)(n+3)|6$

Now rexpanding this we get

$\displaystyle n^3+6n^2+11n+6|6$

Rewriting this we get

$\displaystyle n^3+6n^2+11n+6=n^3+3n^2+2n+3n^2+9n+6=n^3+3n^2+2n+3 (n+1)(n+2)|6$

Now by our hypothesis the first term is divisible by six, so it follows that we must just prove that $\displaystyle 3(n+1)(n+2)|6$

Now if $\displaystyle n$ is odd then $\displaystyle n+1$ is even so $\displaystyle n+1|2$

So there is a factor of two in $\displaystyle n+1$ so there is a factor of six in $\displaystyle 3(n+1)$ and consequently in $\displaystyle 3(n+1)(n+2)$

Now if $\displaystyle n$ is even then $\displaystyle n+2$ is even and the same argument follows.

So we have proved our iductive step and the result follows.

EDIT: Moo has informed me that I have the notation backwards, for my sake just pretend that $\displaystyle n(n+1)(n+2)|6$ means that the left hand side is divides the right hand site. - Nov 22nd 2008, 12:01 PMxoluosox
Thank you so much. I didn't know how to set up the equation at all.

- Nov 22nd 2008, 12:10 PMo_O
A note on notation.

When you say $\displaystyle n^3 + 2n^2+2n$ is divisible by 6 (or 6 divides $\displaystyle n^3 + 2n^2 + 2n$ ), we write it like this $\displaystyle 6 \mid (n^3 + 2n^2 + 2n)$.

_________________________

Also in the inductive step, you can simply factor out the 3 in that second term and use the fact that if you add two numbers that are divisible by 3, then their sum is also divisible by 3:

$\displaystyle \begin{aligned}(n+1)^3 + 3(n+1)^2 + 2(n+1) & = (n+1)(n+2)(n+3) \\ & = n^3 + 6n^2 + 11n + 6 \\ & = n^2 + 3n^2 + 2n + 3n^2 + 9n + 6 \\ & = \underbrace{(n^2 + 3n^2 + 2n)}_{\text{Inductive Hypothesis}} + \underbrace{3(n^2 + 6n + 3)}_{\text{Clearly divisible by 3}} \end{aligned}$ - Nov 22nd 2008, 12:58 PMSoroban
Hello, xoluosox!

The proof depends upon what methods you are allowed.

. . Direct algebraic proof? .Induction?

Quote:

Prove that 6 is a factor of $\displaystyle n^3+3n^2+2n$ for all natural numbers $\displaystyle n.$

Factor the polynomial: .$\displaystyle n(n+1)(n+2)$

We have the product of*three consecutive integers.*

Since they must be: .$\displaystyle \text{(odd)} \times \text{(even)} \times \text{(odd)}\;\text{ or }\;\text{(even)} \times \text{(odd)} \times \text{(even)}$

. . at least one of the factors is even.

Hence, the polynomial is divisible by 2.

It can be shown (you can devise your own proof) that:

. . the product of three consecutive integers is divisible by 3.

Got it?

- Nov 22nd 2008, 01:04 PMmr fantastic
The first two steps should be obvius.

Now you have to show that $\displaystyle (k+1)^3 + 3 (k+1)^2 + 2(k+1)$ is divisible by 6 under the assumption that $\displaystyle k^3 + 3 k^2 + 2k$ is divisible by 6.

Note that $\displaystyle (k+1)^3 + 3 (k+1)^2 + 2(k+1) = k^3 + 6 k^2 + 11k + 6 = k^3 + 3 k^2 + 2k + (3k^2 + 9k + 6) = \, ....$

where you now need to think about $\displaystyle 3k^2 + 9k + 6 \, ....$