Exercise 4. Let P (n) be the statement that a postage of n cents can be...

Exercise 4. 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 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.

Exercise 5. Use strong induction to show that every positive integer n can be written as a sum of distinct powers of two, that is, as a sum of a subset of the integers 20 =1,21 =2,22 =4, and so on. [Hint: For the inductive step, separately con- sider the case where k + 1 is even and where it is odd. When it is even, note that (k + 1)/2 is an integer.]

Solutions

Expert Solution

5))

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

(i) T(n) denote the number of distinct ways that a postage of n cents, where n...

(i) T(n) denote the number of distinct ways that a postage of n cents, where n ≥ 4 and n is even, can be made by 4-cent and 6-cent stamps. Find a recurrence relation T(n). NOTE [4,6] is the same as [6,4] so T(10) = 1 so T(n) is NOT T(n-4)+T(n-6) (ii) Now assume we have 10-cent stamps in addition to the previous 2 kinds. Find a recurrence relation, S(n), for the number of distinct ways that a postage of...

(i) T(n) denote the number of distinct ways that a postage of n cents, where n...

(i) T(n) denote the number of distinct ways that a postage of n cents, where n ≥ 4 and n is even, can be made by 4-cent and 6-cent stamps. Give a recursive algorithm (written in Python) to compute T(n) for n ≥ 4 and n is even. Brieﬂy explain why the algorithm is correct but no formal proof is required. NOTE [4,6] is the same as [6,4] so T(10) = 1. (ii) Now assume we have 10-cent stamps in...

Prove that it is possible to make up any postage of n-cents using only 5-cent and...

Prove that it is possible to make up any postage of n-cents using only 5-cent and 9-cent stamps for n ≥ 35.

Prove that any amount of postage greater than or equal to 14 cents can be built...

Prove that any amount of postage greater than or equal to 14 cents can be built using only 3-cent and 8-cent stamps

Let A be a diagonalizable n × n matrix and let P be an invertible n...

Let A be a diagonalizable n × n matrix and let P be an invertible n × n matrix such that B = P−1AP is the diagonal form of A. Prove that Ak = PBkP−1, where k is a positive integer. Use the result above to find the indicated power of A. A = 6 0 −4 7 −1 −4 6 0 −4 , A5 A5 =

7. Let n ∈ N with n > 1 and let P be the set of...

7. Let n ∈ N with n > 1 and let P be the set of polynomials with coefficients in R. (a) We define a relation, T, on P as follows: Let f, g ∈ P. Then we say f T g if f −g = c for some c ∈ R. Show that T is an equivalence relation on P. (b) Let R be the set of equivalence classes of P and let F : R → P be...

Let A be a diagonalizable n × n matrix and let P be an invertible n...

Exercise 4 (Indicator variables). Let (Ω, P) be a probability space and let E ⊆ Ω...

Exercise 4 (Indicator variables). Let (Ω, P) be a probability space and let E ⊆ Ω be an event. The indicator variable of the event E, which is denoted by 1E , is the RV such that 1E (ω) = 1 if ω ∈ E and 1E(ω)=0ifω∈Ec.Showthat1E isaBernoullivariablewithsuccessprobabilityp=P(E). Exercise 5 (Variance as minimum MSE). Let X be a RV. Let xˆ ∈ R be a number, which we consider as a ‘guess’ (or ‘estimator’ in Statistics) of X . Let...

Are the following statements true or false? 1. Let P(n) be the statement "If any string...

Are the following statements true or false? 1. Let P(n) be the statement "If any string of length n over {a, b} has more a's than b's, then it has two a's in a row". We can prove this statement is true for all n with n ≥ 2 by proving P(2), P(3), and "for all n: P(n) → P(n+2)". 2. Let P(x) be a predicate with one free variable x of type natural. If I prove P(0), "for all...

Let P(n) := ” If n^3 is odd then n is also odd.” I.e., if ∃k...

Let P(n) := ” If n^3 is odd then n is also odd.” I.e., if ∃k ∈ Z, n3 = 2k + 1, ∃b ∈ Z, n = 2b + 1 a) Prove P(n) by contraposition b) Prove P(n) contradiction c) Prove P(n) using induction

Subjects