# Mathematical Induction help needed

by matrix_204
Tags: induction, mathematical
 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 non-negative 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.
 HW Helper Sci Advisor P: 3,149 Assume it's true for n. Then for n+1 $$n+1 = 7a'+3b'$$ so that $$n = 7a'+3b'-1 = 7a' + 3 b' + 6 - 7 = 7(a'-1) + 3(b'+2)$$ Just set a' - 1 = a and b' +2 = b and you have your proof.
 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
PF Patron
Thanks
Emeritus
P: 38,400

## Mathematical Induction help needed

Isn't there a crucial step in induction missing? What happens when n= 12?
 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.
 P: 187 Yes, it must first be proven that the statement is true for 12, then go on to show it is true for n+1
 P: 102 so how do we prove it for 12, if we dont know a and b?
P: 1,443
 Quote by matrix_204 so how do we prove it for 12, if we dont know a and b?
firstly you said a => 2 and b => 2 for n => 12

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

then assume it for k and follow the steps given to you before me
 PF Patron Sci Advisor Emeritus P: 11,137 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.
PF Patron
Emeritus
P: 5,539
 Quote by matrix_204 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.
It looks to me like you don't have a feel for the induction process yet.

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.
 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
P: 646
 Quote by matrix_204 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
beeeeeeeeeeeep ..........
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

 Related Discussions Math & Science Software 4 Math & Science Software 3 Math & Science Software 8 Math & Science Software 5 Math & Science Software 15