Let p(n) be the statement that a postage of n cents can be formed using just 4-cents stamps and 7-cent stamps. The parts of this exercise outline a strong in- duction proof that p(n) is true for all integers n ≥ 18.
(a) Show that the statements P (18), P (19), P (20), and P (21) are true, completing the basis step of a proof by strong induction that p(n) is true for all integers n ≥ 18.
(b) What is the inductive hypothesis of a proof by strong induction that p(n) is true for all integers n ≥ 18?
(c) What do you need to prove in the inductive step of a proof that p(n) is true for all integers n ≥ 18?
Copyright By PowCoder代写 加微信 powcoder
(d) Complete the inductive step for k ≥ 21.
(e) Explain why these steps show that P (n) is true for all integers n ≥ 18.
Determine which amounts of postage can be formed using just 3-cent and 10-cent stamps.
1/2 CSI2101/UOttawa/MdH/W22
Find the flaw with the following “proof” that every postage of three cents or more can be formed using just 3-cent and 4-cent stamps.
Basis Step: We can form postage of three cents with a single 3-cent stamp and we can form postage of four cents using a single 4-cent stamp.
Inductive Step: Assume that we can form postage of j cents for all nonnegative in- tegers j with j ≤ k using just 3-cent and 4-cent stamps. We can then form postage of k + 1 cents by replacing one 3-cent stamp with a 4-cent stamp or by replacing two 4-cent stamps by three 3-cent stamps.
Problem 4 (Example 10, Sec. 8.2)
Find all solutions of the recurrence relation an = 3an−1 + 2n. What is the solution with a1 = 3?
2/2 CSI2101/UOttawa/MdH/W22
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com