testing header
Math Goodies is a free math help portal for students, teachers, and parents.
Free Math
Newsletter
 
 
Interactive Math Goodies Software

Buy Math Goodies Software
testing left nav
Math Forums @ Math Goodies
Math Forums @ Math Goodies
Home | Profile | Register | Active Topics | Members | Search | FAQ
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 Homework Help Forums
 Miscellaneous Math Topics
 Mathematical Induction (Prove)
 New Topic  Reply to Topic
 Printer Friendly
Author Previous Topic Topic Next Topic  

Dmitry M.
Average Member

USA
7 Posts

Posted - 10/21/2007 :  14:28:28  Show Profile  Reply with Quote
Hello, i'm new to the forum. I'm currently majoring in Math at my local university. I'm taking a math course called Discrete Mathematical Structures and have some homework questions which i'm having trouble solving. I was hoping someone could help me in solving them and explain how they got to that point.

1. Use mathematical induction to prove that: 4^(n) - 1 is divisible by 3 for all n.

2. Use mathematical induction to prove that:
1+2+...+n<((n+1)/2)

3. Use induction to prove the following statement:
"If p is a prime and p divides a^(n) for n>1, then p must divide a itself."

4. Prove that the sum of two prime numbers, each larger than 2, is not a prime number. (Note: This does not require induction)

Any help is appreciated, and thanks to anyone and everyone in advance.
Go to Top of Page

pka
Advanced Member

USA
2731 Posts

Posted - 10/21/2007 :  16:25:34  Show Profile  Reply with Quote
Here is help with #1.
4K+1-1=4K+1+4-4-1=4(4K-1)+(3).
If 4K-1 is divisible by three then so is 4K+1-1. WHY?

Help on #4.
The sum of two odd integers is even.
Any prime greater than 2 is odd.
Go to Top of Page

Dmitry M.
Average Member

USA
7 Posts

Posted - 10/21/2007 :  18:14:43  Show Profile  Reply with Quote
quote:
Originally posted by pka

Here is help with #1.
4K+1-1=4K+1+4-4-1=4(4K-1)+(3).
If 4K-1 is divisible by three then so is 4K+1-1. WHY?

Help on #4.
The sum of two odd integers is even.
Any prime greater than 2 is odd.




So for #1 it is so because 4K+1-1 = 4(4K-1)+(3) and we know that for any multiple of 4K-1 it will be divisible by 3 and 3 is divisible by 3.
Go to Top of Page

galactus
Advanced Member

USA
1464 Posts

Posted - 10/21/2007 :  18:15:19  Show Profile  Reply with Quote
For #2:

The base case, n=1 is true since 1<2

Assume P_k is true and show for P_(k+1):

1+2+3+........+k<((k+1)^2/2).

Show

1+2+3+..........+k+(k+1)<[(k+1)^2]/2+(k+1)

1+2+3+........+k+(k+1)<((k+1)(k+3))/2

2+4+6+..........+2k+2(k+1)<(k+1)(k+3)

But the sum of the first 2(k+1) even integers is k(k+3)

So, k(k+3)<(k+1)(k+3)....QED

As was to be shown

Go to Top of Page

Dmitry M.
Average Member

USA
7 Posts

Posted - 10/21/2007 :  19:00:05  Show Profile  Reply with Quote
What is QED?
Go to Top of Page

pka
Advanced Member

USA
2731 Posts

Posted - 10/21/2007 :  20:04:43  Show Profile  Reply with Quote
quote:
Originally posted by Dmitry M.What is QED?

Don't be so lazy. Look it up!
http://en.wikipedia.org/wiki/Q.E.D.
Go to Top of Page

badgerigar
Average Member

Australia
8 Posts

Posted - 11/03/2007 :  01:23:00  Show Profile  Reply with Quote
for #3 try looking at the contrapositive of the thing your proving. Then it gets easy.
Go to Top of Page
  Previous Topic Topic Next Topic  
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
Math Forums @ Math Goodies © 2000-2004 Snitz Communications Go To Top Of Page
This page was generated in 0.06 seconds. Snitz Forums 2000
testing footer
About Us | Contact Us | Advertise with Us | Facebook | Blog | Recommend This Page




Copyright © 1998-2014 Mrs. Glosser's Math Goodies. All Rights Reserved.

A Hotchalk/Glam Partner Site - Last Modified 22 Apr 2014