induction q (harder 3U) (1 Viewer)

[AGB]

can someone please help me??

use induction to prove the following for n greater than/equal 1

n^5 + n^3 + 2n is divisible by 4


i am stuck

 

[Affinity]

sort of messy:

1^5 + 1^3 + 2 = 4 is divisible by 4

so the proposition is true for n = 1

now to prove that if the proposition is true for n=k then it is true for n = k+1

the induction hypothesis is therefore k^5 +k^3 + 2k =4a for some integer a.

(k+1)^5 + (k+1)^3 + 2(k+1)

= k^5 + 5k^4 +11k^3 + 13k^2 + 10k + 4

= (k^5 + k^3 + 2k) + 4k^4 + 8k^3 + 12k^2 +8k + 4 + k^4 + 2k^3 +k^2

= 4(a + k^4 + 2k^3 + 3k^2 + 2k + 1) + k^2(k+1)^2

= 4b +k^2(k+1)^2 for some integer b

now, one and only one of k or k+1 must be even, and the square of even numbers must be multiples of 4 so k^2(k+1)^2 must be a multiple of 4.

above
=4b + 4c for some c
= 4(b+c) which is divisible by 4

so the proposition being true for k implies it's true for n=k+1

by the principle of mathematical induction, it's true for n E {1,2,...}

I WANT TO USE MOD ARITHMETIC

 

[Fosweb]

Originally posted by Affinity
I WANT TO USE MOD ARITHMETIC

Not in our course... Pity though. Mod and PhP is nice.

 

[Affinity]

if it wasn't for the word INDUCTION

n^5 + n^3 +2n

=n^5 + n^3 -2n +4n

= n(n^4 +n^2 -2) + 4n
=n(n+1)(n-1)(n^2 + 2) +4n

now if n is even, then n^2, n^2 +2 will be even

the product n(n^2 + 2) will be the product of 2 even numbers, hence a multiple of four

if n is odd, then (n-1) and (n+1) will be both even and their product will be a multiple of 4

so for any n

n(n+1)(n-1)(n^2 + 2) is a multiple of 4
hence

n^5 + n^3 + 2n=n(n+1)(n-1)(n^2 + 2) + 4n is also a multuple of 4

 

[turtle_2468]

Hmm... here's an induction proof which is shorter.
1) n=1 obviously.
2) Suppose true for n=k. Now consider n=k+1. If n is even we are done (sub 2x etc). For n odd, n^5+n^3+2n=n+n+2n (as n^3=n mod 4) thus it is divisible by 4.
3) as normal
The reasoning is that induction only requires you to put in the steps, ie you could prove really stupid things using induction but only putting the "actual shorter" proof within the induction framework... you have to admit that was an induction proof above! If you want to be nitpicky and say I need to use induction hypothesis, I'll just say (k+1)^5+(k+1)^3+2(k+1)^2= (k+1)^5+(k+1)^3+2(k+1)^2 + k^5+k^3+2k and we know both of these are div by 4 (partly by inductive hypothesis) hence true.

Granted, it might piss off the markers in HSC and lose you a few marks, but if you got the chance to talk to the marker it's guaranteed full marks in most cases...

 

[freaking_out]

Originally posted by turtle_2468
Hmm... here's an induction proof which is shorter.
1) n=1 obviously.
2) Suppose true for n=k. Now consider n=k+1. If n is even we are done (sub 2x etc). For n odd, n^5+n^3+2n=n+n+2n (as n^3=n mod 4) thus it is divisible by 4.
3) as normal
The reasoning is that induction only requires you to put in the steps, ie you could prove really stupid things using induction but only putting the "actual shorter" proof within the induction framework... you have to admit that was an induction proof above! If you want to be nitpicky and say I need to use induction hypothesis, I'll just say (k+1)^5+(k+1)^3+2(k+1)^2= (k+1)^5+(k+1)^3+2(k+1)^2 + k^5+k^3+2k and we know both of these are div by 4 (partly by inductive hypothesis) hence true.

Granted, it might piss off the markers in HSC and lose you a few marks, but if you got the chance to talk to the marker it's guaranteed full marks in most cases...

yeah, u'd prolly hope drbuchanan was markin' your exams.