Mathematical Induction Help: Proving 7a+3b>=12 for n>=12 using Induction

Click For Summary

Discussion Overview

The discussion revolves around proving the statement that for all integers n ≥ 12, there exist non-negative integers a and b such that n = 7a + 3b, using mathematical induction. Participants explore the steps necessary for constructing an induction proof, including verifying the base case and the inductive step.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant expresses difficulty in starting the induction proof and seeks guidance on how to proceed.
  • Another participant suggests assuming the statement is true for n and then demonstrating it for n + 1, providing a transformation of the equation.
  • Several participants emphasize the necessity of proving the base case for n = 12 before proceeding with the induction step.
  • There is a discussion about how to find appropriate values for a and b for the base case, with suggestions of trial and error and specific calculations.
  • One participant critiques another for not addressing the initial case adequately, highlighting the importance of proving P(12) as part of the induction process.
  • Some participants engage in a debate about the logical structure of induction, particularly the implications of proving or disproving the statement for n.
  • Another participant provides a specific example to demonstrate that the statement holds for n = 12.

Areas of Agreement / Disagreement

Participants generally agree on the necessity of proving the base case for n = 12 and the inductive step for n + 1. However, there is some disagreement regarding the clarity of the induction process and the logical implications of the statements made about induction.

Contextual Notes

Some participants note that the proof relies on finding non-negative integers a and b, which has not been explicitly resolved for the base case. There is also a lack of consensus on the logical structure of the induction argument presented.

Who May Find This Useful

Students learning about mathematical induction, particularly in the context of number theory or algebraic proofs, may find this discussion helpful.

matrix_204
Messages
99
Reaction score
0
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. please 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.
 
Physics news on Phys.org
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.
 
aaaah, now i understand.. thanks a lot, i didn't bother going any further after writing n+1=7a+3b. i really really appreciate the help, thanks again
 
Isn't there a crucial step in induction missing? What happens when n= 12?
 
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.
 
Yes, it must first be proven that the statement is true for 12, then go on to show it is true for n+1
 
so how do we prove it for 12, if we don't know a and b?
 
matrix_204 said:
so how do we prove it for 12, if we don't 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
 
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.
 
Last edited:
  • #10
matrix_204 said:
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[/color]
P(12)-->P(13) because P(12)-->P(12+1), and P(12) is true[/color]
P(13)-->P(14) because P(13)-->P(13+1), and P(13) is true[/color]
.
.
.

and so on.
 
  • #11
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
 
  • #12
matrix_204 said:
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
 

Similar threads

[L'Hospital's Rule] Can I Use Mathematical Induction to Prove This?
  • · Replies 6 ·
Replies
6
Views
2K
Mathematical Induction with binomial sum
  • · Replies 9 ·
Replies
9
Views
4K
If p is even and q is odd, then ##\binom{p}{q}## is even
  • · Replies 19 ·
Replies
19
Views
4K
Mathematical Induction Problem Fibonacci numbers
  • · Replies 11 ·
Replies
11
Views
5K
Mathematica Proof by mathematical induction
  • · Replies 5 ·
Replies
5
Views
8K
Undergrad Use of induction in the proof of the Chinese Remainder Theorem
  • · Replies 7 ·
Replies
7
Views
3K
Prove that ##5 | (2^n a) \rightarrow (5 | a)##for any ##n##
  • · Replies 10 ·
Replies
10
Views
4K
Prove Fibonacci identity using mathematical induction
  • · Replies 4 ·
Replies
4
Views
4K
Prove this inequality using induction
  • · Replies 2 ·
Replies
2
Views
2K
Proof by mathematical induction
  • · Replies 4 ·
Replies
4
Views
2K