Math Forums @ Math Goodies - Mathematical Induction (Prove)

testing header

Math Goodies is a free math help portal for students, teachers, and parents.

| More

Interactive Math Goodies Software

Math Forums @ Math Goodies

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

Topic

Dmitry M.
Average Member

USA
7 Posts

Posted - 10/21/2007 : 14:28:28

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.

pka
Advanced Member

USA
2731 Posts

Posted - 10/21/2007 : 16:25:34

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

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

Dmitry M.
Average Member

USA
7 Posts

Posted - 10/21/2007 : 18:14:43

quote:
Originally posted by pka

Here is help with #1.
4^K+1-1=4^K+1+4-4-1=4(4^K-1)+(3).
If 4^K-1 is divisible by three then so is 4^K+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 4^K+1-1 = 4(4^K-1)+(3) and we know that for any multiple of 4^K-1 it will be divisible by 3 and 3 is divisible by 3.

galactus
Advanced Member

USA
1464 Posts

Posted - 10/21/2007 : 18:15:19

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

Dmitry M.
Average Member

USA
7 Posts

Posted - 10/21/2007 : 19:00:05

What is QED?

pka
Advanced Member

USA
2731 Posts

Posted - 10/21/2007 : 20:04:43