Mathematical induction

Printable View

November 22nd 2008, 11:41 AM
xoluosox

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.
November 22nd 2008, 11:58 AM
Mathstud28

Quote:

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?

http://www.mathhelpforum.com/math-he...c/progress.gif THANKS SO MUCH.

Ok so our hypothesis is that $n^3+3n^2+2n=n(n+1)(n+2)|6~\forall{n}\in\mathbb{N}$

So lets begin

Base Step: $n=1$

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

So that is true

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

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

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

Now rexpanding this we get

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

Rewriting this we get

$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 $3(n+1)(n+2)|6$

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

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

Now if $n$ is even then $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 $n(n+1)(n+2)|6$ means that the left hand side is divides the right hand site.
November 22nd 2008, 12:01 PM
xoluosox

Thank you so much. I didn't know how to set up the equation at all.
November 22nd 2008, 12:10 PM
o_O

A note on notation.

When you say $n^3 + 2n^2+2n$ is divisible by 6 (or 6 divides $n^3 + 2n^2 + 2n$ ), we write it like this $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:
$\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}$
November 22nd 2008, 12:58 PM
Soroban

Hello, xoluosox!

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

Quote:

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

Here's one approach . . .

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

We have the product of three consecutive integers.

Since they must be: . $\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?
November 22nd 2008, 01:04 PM
mr fantastic

Quote:

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 $(k+1)^3 + 3 (k+1)^2 + 2(k+1)$ is divisible by 6 under the assumption that $k^3 + 3 k^2 + 2k$ is divisible by 6.

Note that $(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 $3k^2 + 9k + 6 \, ....$