Author Topic: Induction proof question (Read 1529 times) Tweet Share

rife168 · « **on:** February 24, 2012, 11:39:58 am »

I am having a bit of trouble with the following question:

Use mathematical induction to prove the following results $\forall n\in \mathbb{N}$

$n(n^2+5)$ is divisible by 6

kamil9876 · « **Reply #1 on:** February 24, 2012, 12:04:27 pm »

Well the base case $n=1$ is easy since the expression is equal to $6$ .

Now suppose that $n(n^2+5)$ is divisible by $6$ . I.e $n(n^2+5)=6m$ for some natural number $m$ .

Now

$(n+1)((n+1)^2+5)$

$=(n+1)((n^2+5)+(2n+1))$

$=n(n^2+5) + n(2n+1)+n^2+5+2n+1$

$=6m + 3n^2+3n+6$

$=6m+3n(n+1)+6$

So we are done if we can show that $3n(n+1)$ is a multiple of 6, but this is obvious as one of either $n$ or $n+1$ is even.

TrueTears · « **Reply #2 on:** February 24, 2012, 12:59:50 pm »

Although kamil's answered the question, I just want to provide another way of looking at this question.

If we assume $n(n^2+5)$ is divisible by 6 then $n(n^2+5) \equiv n(n^2-1) \equiv n(n-1)(n+1) \pmod 6$

Now you have the product of 3 consecutive numbers, what can you deduce from them?

rife168 · « **Reply #3 on:** February 26, 2012, 12:14:51 am »

Quote from: TrueTears on February 24, 2012, 12:59:50 pm

Although kamil's answered the question, I just want to provide another way of looking at this question.

If we assume $n(n^2+5)$ is divisible by 6 then $n(n^2+5) \equiv n(n^2-1) \equiv n(n-1)(n+1) \pmod 6$

Now you have the product of 3 consecutive numbers, what can you deduce from them?

Hmm, not sure..
Would I be right in assuming that the product of 3 consecutive natural numbers will always be even?

edit: oh! so that means that it will be divisible by 2. Also, there will be 1 term which is divisible by 3. Hence 6 must be a factor!
Thanks TT

TrueTears · « **Reply #4 on:** February 26, 2012, 12:23:21 am »

Quote from: fletch-j on February 26, 2012, 12:14:51 am

Quote from: TrueTears on February 24, 2012, 12:59:50 pm
Although kamil's answered the question, I just want to provide another way of looking at this question.

If we assume $n(n^2+5)$ is divisible by 6 then $n(n^2+5) \equiv n(n^2-1) \equiv n(n-1)(n+1) \pmod 6$

Now you have the product of 3 consecutive numbers, what can you deduce from them?

Hmm, not sure..
Would I be right in assuming that the product of 3 consecutive natural numbers will always be even?

edit: oh! so that means that it will be divisible by 2. Also, there will be 1 term which is divisible by 3. Hence 6 must be a factor!
Thanks TT

correct

rife168 · « **Reply #5 on:** February 26, 2012, 09:45:35 am »

Another Question (not so much about induction):

i) Prove that if n is an odd integer, then n³ is odd.

ii) Deduce from this that for any integer m, if m³ is even, then so is m.

I have done part i) and I think that I can do part ii), but how can I deduce it from part i)?

kamil9876 · « **Reply #6 on:** February 26, 2012, 10:44:29 pm »

It's just what is known as taking the contrapositive i.e A implies B is logically the same as (not B) implies (not A). (i.e "all widgets are gadgets" is the same as saying that "anything that is not a gadget is not a widget")

Specifically here: Suppose it was false, that means there exists an integer $m$ such that $m^3$ is even but $m$ is odd. But if $m$ is odd then by part i $m^3$ is odd which is a contradiciton.

rife168 · « **Reply #7 on:** February 26, 2012, 11:00:04 pm »

Thanks Kamil, got it!

Search the forums now!

We have moved!

Author Topic: Induction proof question (Read 1529 times) Tweet Share

rife168

Induction proof question

kamil9876

Re: Induction proof question

TrueTears

Re: Induction proof question

rife168

Re: Induction proof question

TrueTears

Re: Induction proof question

rife168

Re: Induction proof question

kamil9876

Re: Induction proof question

rife168

Re: Induction proof question

Recent Posts

User:
Password: