1. ## Mathematical 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.

2. Originally Posted by xoluosox
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.
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.

3. Thank you so much. I didn't know how to set up the equation at all.

4. 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}

5. Hello, xoluosox!

The proof depends upon what methods you are allowed.
. . Direct algebraic proof? .Induction?

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

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?

6. Originally Posted by xoluosox
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.
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 \, ....$