What's wrong with this induction proof for 2 and 3-cent stamps?

  • Context: Undergrad 
  • Thread starter Thread starter PhysicsHelp12
  • Start date Start date
  • Tags Tags
    Induction Proof
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 2K views
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.