Mathematical Induction and proofs

  • Mathematica
  • Thread starter richievuong
  • Start date
  • #1

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?
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,260
619
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?
 
  • #3
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?
 
Last edited:
  • #4
Dick
Science Advisor
Homework Helper
26,260
619
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.
 
  • #5
f(n+2) = (n+2)³ - 4(n+2)
= n³+6n²+8n

where do i go from here?
 
  • #6
Dick
Science Advisor
Homework Helper
26,260
619
Well, we get to ASSUME f(n) is divisible by 48. How might we show this f(n+2) is also divisible by 48?
 
  • #7
682
1
factor........
 
  • #8
Dick
Science Advisor
Homework Helper
26,260
619
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.
 
  • #9
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)
 
  • #10
Dick
Science Advisor
Homework Helper
26,260
619
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?).
 
  • #11
6n² + 12n....
so then n = 2k cause its even

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

is that it?
 
  • #12
Dick
Science Advisor
Homework Helper
26,260
619
I see that it is divisible by 24. Why is it divisible by 48?
 
  • #13
i dont know lol i'm so close....

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

and 2 x 24 = 48?
 
  • #14
Dick
Science Advisor
Homework Helper
26,260
619
Your answer is 24*(k^2+k). Is k^2+k odd or even (where k can be either even or odd)?
 
  • #15
k²+k has to be even for any value of k.....so therefore its divisible by 2?
 
  • #16
Dick
Science Advisor
Homework Helper
26,260
619
Yes. So 24*(k^2+k) is divisible by what?
 
  • #17
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)
 
  • #18
Dick
Science Advisor
Homework Helper
26,260
619
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.
 

Related Threads on Mathematical Induction and proofs

Replies
14
Views
4K
Replies
10
Views
4K
Replies
3
Views
30K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
5
Views
3K
Top