Register to reply 
Mathematical Induction help needed 
Share this thread: 
#1
Oct404, 10:24 PM

P: 102

i was having trouble coming up with an induction proof for this problem, although i have tried and was able to prove it sumhow(using numbers 1 n so forth, teacher doesn't allow us to use them yet), but not using induction. I have no clue on how to do this using induction. plz help me.
Problem: Prove that for all n>=12, there are nonnegative integers a and b such that n=7a+3b. THen note that if a,b are integers such that 7a+3b>=12, then a>=2 and b>=2. Then put the above property so that having the expression n of the type (n=7a+3b) gives an expression for n+1 also for the type (n=7a+3b). how am i suppose to start this proof, using induction and using facts if needed. 


#2
Oct404, 10:45 PM

Sci Advisor
HW Helper
P: 3,144

Assume it's true for n. Then for n+1
[tex]n+1 = 7a'+3b'[/tex] so that [tex]n = 7a'+3b'1 = 7a' + 3 b' + 6  7 = 7(a'1) + 3(b'+2)[/tex] Just set a'  1 = a and b' +2 = b and you have your proof. 


#3
Oct404, 11:04 PM

P: 102

aaaah, now i understand.. thanx alot, i didn't bother going any further after writing n+1=7a+3b. i really really appreciate the help, thanx again



#4
Oct504, 07:01 AM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,489

Mathematical Induction help needed
Isn't there a crucial step in induction missing? What happens when n= 12?



#5
Oct504, 07:24 PM

P: 102

aren't we suppose to assume it is true for the first number, for example n=12, and then prove for the next number n+1.



#6
Oct504, 07:44 PM

P: 186

Yes, it must first be proven that the statement is true for 12, then go on to show it is true for n+1



#7
Oct504, 07:58 PM

P: 102

so how do we prove it for 12, if we dont know a and b?



#8
Oct504, 08:03 PM

P: 1,439

7(2) + 3(2) = 14 + 6 = 20 => 12 and this is true for the first allowed case for 12 since 20 => 12, the last time i checked thats your first step then assume it for k and follow the steps given to you before me 


#9
Oct504, 08:06 PM

Emeritus
Sci Advisor
PF Gold
P: 11,155

Matrix, can you not find a, b by simple trial and error ? It hardly takes a couple of tries before you find the right values.
Stunner, you are not answering matrix's question about the initial case. 


#10
Oct504, 08:12 PM

Emeritus
Sci Advisor
PF Gold
P: 5,532

Just to elaborate one what Spectre said, you have to prove that the statement P(n) is true for n=12. In fact, if you don't do that, you will only prove the conditional statement: If P(n) is true, then P(n+1) is true. Well what if P(n) is not true? That's why both steps are needed. When both P(12) and P(n)>P(n+1) are proven, then the proof holds for all n>=12 by the domino effect. P(12) is true. proven directly P(12)>P(13) because P(12)>P(12+1), and P(12) is true P(13)>P(14) because P(13)>P(13+1), and P(13) is true . . . and so on. 


#11
Oct504, 08:22 PM

P: 102

If P(n) is not true, then P(n+1) is true. p(n)=>p(n+1) then P(n) must be true, according to the truth table



#12
Oct504, 08:33 PM

P: 646

check the truth table again ..... given a statement p>q if p is false and q is true, p>q is still true so given the truth values of q and p>q , one cannot determine the truth value of p. If that were so , most of the modus ponen rules i study in AI would come to nought!!! really!!  AI P.S> 7*0+3*4 = 12 


Register to reply 
Related Discussions  
Mathematical Induction  Math & Science Software  4  
Mathematical Induction Help Needed  Math & Science Software  3  
Mathematical Induction  Math & Science Software  8  
Mathematical Induction  Math & Science Software  5  
Mathematical Induction  Math & Science Software  15 