Mathematical Induction help needed

matrix_204

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.

Tide

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

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

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

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.

Spectre5

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

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

stunner5000pt

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

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

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

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

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