1. Induction

Induction Proof
n(n^2 + 5) is divisible by 6 for all integers n >= 1.
i am kind of stuck here

2. Originally Posted by neelpatel89
Induction Proof
n(n^2 + 5) is divisible by 6 for all integers n >= 1.
i am kind of stuck here

Where EXACTLY are you stuck? Have you already checked for n = 1? Then, what is your inductive asusmption (hypothesis)?
It's possible to do it without induction, too:
(1) if n is an odd multiple of 3 then n^2 is odd and thus n^2 + 5 is even ==> the product n(n^2 + 5) is divisible both by 2 and 3 and thus by 6
(2) if n is an even multiple of 3 then it is a multiple of 6...
(3) if n is NOT a multiple of n the n^2 + 5 is ALWAYS a multiple of 3 (right n = 1 or 2 + 3k,. with k an integer, and square this and add to 5): if n is odd then n^2 + 5 is even, and if n is even good: in any case, the product n(n^2 + 5) is divisible both by 2 and by 3.

Tonio

3. Originally Posted by tonio
Where EXACTLY are you stuck? Have you already checked for n = 1? Then, what is your inductive asusmption (hypothesis)?
It's possible to do it without induction, too:
(1) if n is an odd multiple of 3 then n^2 is odd and thus n^2 + 5 is even ==> the product n(n^2 + 5) is divisible both by 2 and 3 and thus by 6
(2) if n is an even multiple of 3 then it is a multiple of 6...
(3) if n is NOT a multiple of n the n^2 + 5 is ALWAYS a multiple of 3 (right n = 1 or 2 + 3k,. with k an integer, and square this and add to 5): if n is odd then n^2 + 5 is even, and if n is even good: in any case, the product n(n^2 + 5) is divisible both by 2 and by 3.

Tonio
well, i thought about what you said, and i actually got the same thing as you have, but i need to do this using induction, and i have no idea how to start or anything

4. Originally Posted by neelpatel89
well, i thought about what you said, and i actually got the same thing as you have, but i need to do this using induction, and i have no idea how to start or anything
It's obvioulsy true for n = 1.

Assume true for n = m.

Show true for n = m implies true for n = m+1:

$\displaystyle (m + 1)((m+1)^2 + 5) = m(m^2 + 2m + 6) + m^2 + 2m + 6$

$\displaystyle = m(m^2 + 5) + 2m^2 + m + m^2 + 2m + 6 = m(m^2 + 5) + 3m^2 + 3m + 6$

$\displaystyle = m(m^2 + 5) + 3(m^2 + m + 2)$

The first term is divisible by 6 (from the inductive hypothesis). Your job is to prove that the second term, that is, $\displaystyle 3(m^2 + m + 2)$ is divisible by 6. I suggest using induction ....

5. Originally Posted by mr fantastic
It's obvioulsy true for n = 1.

Assume true for n = m.

Show true for n = m implies true for n = m+1:

$\displaystyle (m + 1)((m+1)^2 + 5) = m(m^2 + 2m + 6) + m^2 + 2m + 6$

$\displaystyle = m(m^2 + 5) + 2m^2 + m + m^2 + 2m + 6 = m(m^2 + 5) + 3m^2 + 3m + 6$

$\displaystyle = m(m^2 + 5) + 3(m^2 + m + 2)$

The first term is divisible by 6 (from the inductive hypothesis). Your job is to prove that the second term, that is, $\displaystyle 3(m^2 + m + 2)$ is divisible by 6. I suggest using induction ....
Or simpler, just divide in two cases: odd m and even m. In both cases the expression within the parentheses in even and we're done

Tonio

6. one proof without induction

$\displaystyle n(n^2 + 5)=n^3+5n=6{n \choose 1}+6{n \choose 2}+6{n \choose 3}$