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
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
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,881

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