1) Use strong induction to show that you can make any required postage using just 5-cent stamps and 8-cent stamps for postage

28 cents.*Note that 3 5-cent stamps = 15 cents, and 2 8-cent stamps = 16 cents

Label your steps, A., B., C., D. E. and provideonlythe parts requested in bold text.

A.Write P(n).

B. Basis step:Showthat P(n) works for as manynas you need. Each one should be of the form

"P(n) =x5-cent +y8-cent stamps", or "P(n) =x5-cent stamps", or "P(n) =y8-cent stamps" for x > 0 and y > 0.

C.State the inductive hypothesis,with a correctly definedthe range.

D.Write the inductive stepin the form: "Show that P(___)

P(___) ".

E.Write the one line proofin the form: "We assume P(___) is true by the inductive hypothesis. Then we can add _________ to form P(___) postage".

2) What is the common name of procedure F? (The answer is a single word.)

Procedure F(n: nonnegative integer)

if n = 0 then

return 0

else if n = 1 then

return 1

else

return F(n 1) + F(n 2)