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}+441=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}+441=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 

badgerigar
Average Member
Australia
8 Posts 
Posted  11/03/2007 : 01:23:00

for #3 try looking at the contrapositive of the thing your proving. Then it gets easy. 



Topic 
