Let p(n) be the statement that a postage of n cents can be formed using just 4-cent stamps and 7-cent stamps. the 342 5 / induction and recursion parts of this exercise outline a strong induction proof that p(n) is true for n ≥ 18. a) show statements p(18), p(19), p(20), and p(21) are true, completing the basis step of the proof. b) what is the inductive hypothesis of the proof? c) what do you need to prove in the inductive step? d) complete the inductive step for k ≥ 21. e) explain why these steps show that this statement is true whenever n ≥ 18.

See explanation

Step-by-step explanation:

Statement: P(n) = "a postage of n cents can be formed using just 4-cent stamps and 7-cent stamps".

A. P(18) = a postage of 18 cents can be formed using two 7-cent stamps and one 4-cent stamp.

P(19) = a postage of 19 cents can be formed using one 7-cent stamp and three 4-cent stamps.

P(20) = a postage of 20 cents can be formed using five 4-cent stamps.

P(21) = a postage of 21 cents can be formed using three 7-cent stamps.

B. Inductive hypothesis is to assume that P(n) is true for all n < 18

C. In the inductive step we need to prove that P(n+1) is true.

D. Let k ≥ 21, then

E. Since all natural numbers are of the form 4l, 4l + 1, 4l + 2, 4l + 3, we can state that P(n) is true for all n ≥ 18.

i think it's eleven too, don't woosh me here, but according to the "experts" it's 2.

the proof starts from the peano postulates, which define the natural

numbers n. n is the smallest set satisfying these postulates:

  p1.   1 is in n.

  p2.   if x is in n, then its "successor" x' is in n.

  p3.   there is no x such that x' = 1.

  p4.   if x isn't 1, then there is a y in n such that y' = x.

  p5.   if s is a subset of n, 1 is in s, and the implication

      (x in s => x' in s) holds, then s = n.

then you have to define addition recursively:

  def: let a and b be in n. if b = 1, then define a + b = a'

      (using p1 and p2). if b isn't 1, then let c' = b, with c in n

      (using p4), and define a + b = (a + c)'.

then you have to define 2:

  def:   2 = 1'

2 is in n by p1, p2, and the definition of 2.

theorem:   1 + 1 = 2

proof: use the first part of the definition of + with a = b = 1.

      then 1 + 1 = 1' = 2   q.e.d.

note: there is an alternate formulation of the peano postulates which

replaces 1 with 0 in p1, p3, p4, and p5. then you have to change the

definition of addition to this:

  def: let a and b be in n. if b = 0, then define a + b = a.

      if b isn't 0, then let c' = b, with c in n, and define

      a + b = (a + c)'.

you also have to define 1 = 0', and 2 = 1'. then the proof of the

theorem above is a little different:

proof: use the second part of the definition of + first:

      1 + 1 = (1 + 0)'

      now use the first part of the definition of + on the sum in

      parentheses:   1 + 1 = (1)' = 1' = 2   q.e.d.

step-by-step explanation:

what was your answer?