Register to reply

Mathematical Induction help needed

by matrix_204
Tags: induction, mathematical
Share this thread:
matrix_204
#1
Oct4-04, 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 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.
Phys.Org News Partner Science news on Phys.org
Security CTO to detail Android Fake ID flaw at Black Hat
Huge waves measured for first time in Arctic Ocean
Mysterious molecules in space
Tide
#2
Oct4-04, 10:45 PM
Sci Advisor
HW Helper
P: 3,147
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.
matrix_204
#3
Oct4-04, 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

HallsofIvy
#4
Oct5-04, 07:01 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,346
Mathematical Induction help needed

Isn't there a crucial step in induction missing? What happens when n= 12?
matrix_204
#5
Oct5-04, 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.
Spectre5
#6
Oct5-04, 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
matrix_204
#7
Oct5-04, 07:58 PM
P: 102
so how do we prove it for 12, if we dont know a and b?
stunner5000pt
#8
Oct5-04, 08:03 PM
P: 1,440
Quote 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

thats your first step

then assume it for k and follow the steps given to you before me
Gokul43201
#9
Oct5-04, 08:06 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
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.
Tom Mattson
#10
Oct5-04, 08:12 PM
Emeritus
Sci Advisor
PF Gold
Tom Mattson's Avatar
P: 5,533
Quote 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.
matrix_204
#11
Oct5-04, 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
TenaliRaman
#12
Oct5-04, 08:33 PM
P: 646
Quote 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


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