(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 n cents, where n ≥ 4 and n is even, can be made by 4-cent, 6-cent and 10-cent stamps.

Solutions

Expert Solution

please like ?

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

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

Let An = {ai} n i=1 denote a list of n distinct positive integers. The median...

Let An = {ai} n i=1 denote a list of n distinct positive integers. The median mA of An is a value in An such that half the elements in An are less than m (and so, the other half are greater than or equal m). In fact, the median element is said to have a middle rank. (a) Develop an algorithm that uses Sorting to return mA given An. (6%) (b) Now assume that one is given another list...

Let τ (n) denote the number of positive divisors of n and σ(n) denote the sum...

Let τ (n) denote the number of positive divisors of n and σ(n) denote the sum of the positive divisors of n (as in the notes). (a) Evaluate τ (1500) and σ(8!). (b) Verify that τ (n) = τ (n + 1) = τ (n + 2) = τ (n + 3) holds for n = 3655 and 4503. (c) When n = 14, n = 206 and n = 957, show that σ(n) = σ(n + 1).

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 by induction on n that the number of distinct handshakes between n ≥ 2 people...

Prove by induction on n that the number of distinct handshakes between n ≥ 2 people in a room is n*(n − 1)/2 . Remember to state the inductive hypothesis!

In a sequence of independent flips of a fair coin, let N denote the number of...

In a sequence of independent flips of a fair coin, let N denote the number of flips until there is a run of three consecutive heads. Find P(N ≤ 8). (Should write out transition matrix.)

Let an denote the number of different ways to color the walls of a five-sided room...

Let an denote the number of different ways to color the walls of a five-sided room with n colors if you insist that two walls that meet at a corner must be assigned different colors. (i) compute a1, a2 and a3 directly (ii) Find the formula for an

Let E(n) denote the expected return on asset i and B. denote the corresponding beta. In addition, let E(rm) denote the expected

Let E(n) denote the expected return on asset i and B. denote the corresponding beta. In addition, let E(rm) denote the expected return on the market portfolio and Bm denote the corresponding beta. Define and sketch the Security Market Line (SML). Hint: Use E(rm) - r = 8%, r = 3%, B. = 1.25 and B2 = 0.6.

I have 5 distinct red cards and 4 distinct black cards. a) How many ways can...

I have 5 distinct red cards and 4 distinct black cards. a) How many ways can I choose 1 card? b) How many ways can I choose 1 red card then 1 black card? c) How many ways can I choose 2 cards? Consider a full standard deck of 52 distinct cards. a) How many arrangements of a standard deck of cards are there? That is, what is the total number of possible shuffles? b) How many ways can I...

Subjects