Mathematical Induction and proofs

In summary, the homework statement is true if n is an even positive integer and n³-4n is always divisible by 48. The square of an odd integer is always of the form 8k+1, where k is an integer. The last two digits of 7² are 49, the last two digits of 7³ are 43, the last two digits of 7^4 are 01, and the last two digits of 7^5 are 07. The last two digits of 7^201 are 07.
  • #1
richievuong
35
0

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?
 
Physics news on Phys.org
  • #2
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
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
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
factor...
 
  • #8
tim_lou said:
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
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
I see that it is divisible by 24. Why is it divisible by 48?
 
  • #13
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?
 
  • #14
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
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
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.
 

1. What is mathematical induction?

Mathematical induction is a method of mathematical proof used to establish the truth of a statement for all natural numbers. It involves proving that the statement is true for a base case (usually n=1) and then showing that if the statement is true for some arbitrary value of n, it must also be true for the next value of n (n+1). This process is repeated until the statement is proven to be true for all natural numbers.

2. How is mathematical induction used in proofs?

Mathematical induction is used in proofs to establish the truth of a statement for all natural numbers. It is a powerful tool in mathematics because it allows us to prove statements that hold for an infinite number of cases, without having to explicitly prove each individual case.

3. What is the difference between weak and strong induction?

Weak induction, also known as mathematical induction, involves proving the base case and the inductive step (n to n+1) separately. Strong induction, on the other hand, assumes that the statement is true for all values up to n, and uses this assumption to prove the statement for n+1. In general, strong induction is a more powerful technique, but both methods are valid and can be used to prove the same statements.

4. Can mathematical induction be used to prove any statement?

No, mathematical induction can only be used to prove statements that follow a specific pattern, usually involving natural numbers. It cannot be used to prove statements about real numbers, for example, as there is no "next" real number after a given one.

5. Are there any common mistakes to avoid when using mathematical induction?

One common mistake when using mathematical induction is assuming that the statement must be true for all values of n, rather than just the natural numbers. It is also important to clearly state the base case and inductive hypothesis in the proof and to use proper mathematical notation throughout the process.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
2K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
958
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Replies
13
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
833
  • Precalculus Mathematics Homework Help
Replies
1
Views
666
Back
Top