Proof by Induction: Fixing Errors in Pn | 3-cent and 2-cent Stamps

In summary, the conversation discusses a proof by induction for the statement Pn, which states that any postage of n >= 2 cents can be made using 3-cent and 2-cent stamps. The conversation suggests that there is an issue with the induction step and proposes a way to fix it without changing the step significantly. The conversation also points out that the argument fails when n is 2, and suggests that n must be at least 3 to use n-1 in the argument.
  • #1
PhysicsHelp12
58
0
Let Pn be the statement : any postage of n >= 2 cents can be made of
3-cent and 2-cent stamps. What is wrong with the following proof of
Pn by induction? How can it be fixed without changing the induction
step much?
Base case : 2 = 2 and so P2 is true.
Induction step : Fix some n >=2. Assume that Pk is true for k <= n, we
will prove Pn+1.
Since Pn-1 is true, we know that
n - 1 = a * 2 + b * 3
and hence
n + 1 = (a+1)*2+b*3
 
Physics news on Phys.org
  • #2
Let n be 2: the argument fails. If you want to talk about n - 1 then n has to be at least 3.
 

What is proof by induction?

Proof by induction is a mathematical technique used to prove that a statement is true for all natural numbers. It involves breaking down the statement into smaller cases and proving that each case is true, ultimately showing that the statement is true for all natural numbers.

Why is proof by induction useful?

Proof by induction is useful because it allows us to prove statements that hold true for infinitely many cases. It is a powerful tool in mathematics and is commonly used in fields such as calculus, number theory, and computer science.

What are the steps to conducting a proof by induction?

The steps to conducting a proof by induction are as follows:

  1. Base case: Prove that the statement is true for the first natural number, typically 0 or 1.
  2. Inductive hypothesis: Assume that the statement is true for some arbitrary natural number, k.
  3. Inductive step: Prove that if the statement is true for k, then it is also true for k+1.
  4. Conclusion: By the principle of mathematical induction, the statement is true for all natural numbers.

What are some common mistakes to avoid when using proof by induction?

Some common mistakes to avoid when using proof by induction include:

  • Using the wrong base case.
  • Assuming that the statement is true for k+1 without properly proving it.
  • Using circular reasoning.
  • Not clearly stating the inductive hypothesis.
  • Not addressing all cases in the inductive step.

Can proof by induction be used to prove any statement?

No, proof by induction can only be used to prove statements that are true for all natural numbers. It cannot be used to prove statements that are only true for a finite number of cases or for irrational or negative numbers.

Similar threads

I Spivak, Ch. 20: Understanding a step in the proof of lemma
    • Calculus
Replies
1
Views
1K
B Why do I not understand what seems to be basic Calculus?
    • Calculus
Replies
11
Views
2K
I Resolve the Recursion of Dickson polynomials
    • Calculus
Replies
1
Views
1K
I Looking for Guarantees that the method of fixed-point iteration will work
    • Calculus
Replies
22
Views
1K
I Determination of error in interpolating polynomial
    • Calculus
Replies
5
Views
386
B Attempted proof of the Contracted Bianchi Identity
    • Differential Geometry
Replies
1
Views
1K
Do these two statements imply an underlying induction proof?
    • Calculus and Beyond Homework Help
Replies
7
Views
412
I Is there any way to simplify my proof by induction?
    • General Math
Replies
13
Views
1K
Engineering Calculating Power Losses in an AC Induction Motor
    • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
Prove that ## a^{({2}^{n})}\equiv 1\pmod {2^{n+2}} ## for any ##n##?
    • Precalculus Mathematics Homework Help
Replies
6
Views
1K

Hot Threads

Recent Insights

Back
Top