Mathematical Induction and proofs

[richievuong]

Homework Statement

1. Prove that if n is an even positive integer, then n³-4n is always divisible by 48.

2. Prove taht the square of an odd integer is always of the form 8k+1, where k is an integer.

3. Observe that the last two digits of 7² are 49, the last two digits of 7³ are 43, thel ast two digits of 7^4 are 01, and the last two digits of 7^5 are 07. Prove that the last two digits of 7^201 are 07.

Homework Equations

Don't know if any are applicable.

The Attempt at a Solution

Basically the homework handed out today for my semester 2 discrete and geometry class in high school. I have no experience in proofs and the teacher assigned this without doing any examples :(

I need help on my form and revision on how I attempt these proofs and basically what I can work on to make them look more convincing and professional.

1. Let n = 48k, 48k+2, 48k+4
n³-4n divisible by 48
=(48k)³-4(48)
=110592k³-192k
=192k(576k²-1)
Since 192 is divisible by 48, statement is true.
Should I check with 48k+2, 48k+4 afteR?

2. Since k is an odd integer, we can represent it as 2k+1
(2k+1)² = 8k + 1
4k²+4k+1 = 8k +1
4k²+4k=8k
4k(k+1)=8k
8k is divisible by 4k so statement is true.

3. This one i need help the most.

I figured
7^1 = 7
7^2 = 49
7^3 = 343
7^4 = 2401

and it rotates from 7,9,3,1 (last digit) every 4 numbers...so 7^5 would end with a 7.

so 7^4n+1 would yield a number that ends with 7, 7^4n+2 would yield a number that ends with a 9, etc

so if 7^201 ends with a 7
7^4n+1 = 7^201, n must be an integer
4n+1 = 201
4n = 200
n = 50

Conversely for 7^202
7^4n+1 = 7^202
4n+1 = 202
4n = 201
n is not an integer so 7^202 does not end with a 7.

Getting confused...it looks right sometimes but sometimes it doesn't...am I donig the right stuff?

 

[Dick]

I don't think you quite get mathematical induction. Take 1) and let f(n)=n^3-4*n. You want to prove this is divisible by 48 for n=2,4,6,8... You want to prove two things.

i) f(2) is divisible by 48. (This is the easy part!)

ii) IF f(n) is divisible by 48 THEN f(n+2) is divisible by 48.

Do you see how those two things would prove the result for all positive even n?

 

[richievuong]

ah thank you i think i understand it a bit more now

wait..is it f(n+2) or f(2n) ?
i thought for any even number its 2n and for odd its 2n+1

okay so

f(2) = (2)³ - 4(2) = 0 therefore for n=2 it is true
f(2n) = (2n)³ - 4(2n)
= 8n³ - 8n
= 8n(n²-1)

how do i prove from hereforth that the expression is divisible by 48 for any value of n?

 

[Dick]

No! It is f(n+2). So once you have that it is true for f(2), then ii) tells you it is true for f(2+2)=f(4), which in turn means it's true for f(4+2)=f(6) etc etc.

 

[richievuong]

f(n+2) = (n+2)³ - 4(n+2)
= n³+6n²+8n

where do i go from here?

 

[Dick]

Well, we get to ASSUME f(n) is divisible by 48. How might we show this f(n+2) is also divisible by 48?

 

[tim_lou]

factor...

 

[Dick]

factor...

I don't think it's going to work that way. Besides, we are TRYING to do induction here. That is what the assignment calls for.

 

[richievuong]

wait let me try this again
f(n+2) = (n+2)³ - 4(n+2)
= n³ + 6n² + 12n + 8 -4n - 8

since f(n) = n³-4n and proven that it was divisible by 48

f(n+2) = n³ - 4n + 6n² + 12n
= n³ - 4n + 6n(n+2)

 

[Dick]

Good! So you've shown the difference between f(n+2) and f(n) is 6*n^2+12*n. Can you show that is divisible by 48? (Remember n is even, right?).

 

[richievuong]

6n² + 12n...
so then n = 2k cause its even

6(2k)² + 12(2k)
6(4k²) + 24k
24k² + 24k

is that it?

 

[Dick]

I see that it is divisible by 24. Why is it divisible by 48?

 

[richievuong]

i don't know lol I'm so close...

is it because since i tested f(2) beforehand, 2 is also divisible...

and 2 x 24 = 48?

 

[Dick]

Your answer is 24*(k^2+k). Is k^2+k odd or even (where k can be either even or odd)?

 

[richievuong]

k²+k has to be even for any value of k...so therefore its divisible by 2?

 

[Dick]

Yes. So 24*(k^2+k) is divisible by what?

 

[richievuong]

is divisible by 48...

so since both sides can be divisible by 48...can i conclude that f(n+2) is divisible by 48...and so conclude my whole proof altogether since I've proved both f(n) and f(n+2)

 

[Dick]

QED. It's a stepladder f(2)->f(4)->f(6)->f(8)... Write it up nicely, think about it and try the others in the same spirit.