Mathematical Induction help needed


by matrix_204
Tags: induction, mathematical
matrix_204
matrix_204 is offline
#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
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
Tide
Tide is offline
#2
Oct4-04, 10:45 PM
Sci Advisor
HW Helper
P: 3,149
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
matrix_204 is offline
#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
HallsofIvy is offline
#4
Oct5-04, 07:01 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,898

Mathematical Induction help needed


Isn't there a crucial step in induction missing? What happens when n= 12?
matrix_204
matrix_204 is offline
#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
Spectre5 is offline
#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
matrix_204 is offline
#7
Oct5-04, 07:58 PM
P: 102
so how do we prove it for 12, if we dont know a and b?
stunner5000pt
stunner5000pt is offline
#8
Oct5-04, 08:03 PM
P: 1,445
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
Gokul43201 is offline
#9
Oct5-04, 08:06 PM
Emeritus
Sci Advisor
PF Gold
Gokul43201's Avatar
P: 11,154
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
Tom Mattson is offline
#10
Oct5-04, 08:12 PM
Emeritus
Sci Advisor
PF Gold
Tom Mattson's Avatar
P: 5,540
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
matrix_204 is offline
#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
TenaliRaman is offline
#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