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

  • Context: Undergrad 
  • Thread starter Thread starter PhysicsHelp12
  • Start date Start date
  • Tags Tags
    Induction Proof
Click For Summary
SUMMARY

The discussion addresses the proof by induction for the statement Pn, which asserts that any postage of n >= 2 cents can be constructed using 3-cent and 2-cent stamps. The initial proof fails at the induction step when n = 2, as it incorrectly assumes Pn-1 is valid without ensuring n is at least 3. To correct this, the proof must establish the base case for n = 3 and adjust the induction step accordingly, ensuring that the assumption holds for all n >= 3.

PREREQUISITES
  • Understanding of mathematical induction
  • Familiarity with basic number theory concepts
  • Knowledge of postage stamp problems
  • Ability to construct and analyze mathematical proofs
NEXT STEPS
  • Review the principles of mathematical induction in detail
  • Study the properties of linear combinations in number theory
  • Explore variations of the postage stamp problem
  • Practice constructing proofs for similar mathematical statements
USEFUL FOR

Mathematicians, educators, students studying discrete mathematics, and anyone interested in understanding proof techniques in number theory.

PhysicsHelp12
Messages
58
Reaction score
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
Let n be 2: the argument fails. If you want to talk about n - 1 then n has to be at least 3.
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 11 ·
Replies
11
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 22 ·
Replies
22
Views
3K
  • · Replies 5 ·
Replies
5
Views
3K
  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 13 ·
Replies
13
Views
2K
  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 10 ·
Replies
10
Views
4K
  • · Replies 1 ·
Replies
1
Views
3K