Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help proof by induction

  1. Jan 21, 2009 #1
    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
  2. jcsd
  3. Jan 21, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Let n be 2: the argument fails. If you want to talk about n - 1 then n has to be at least 3.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook