Please explain in great details. Don\'t skip intermediate steps. I am trying to
ID: 3725142 • Letter: P
Question
Please explain in great details. Don't skip intermediate steps. I am trying to really understand this. Thank you
6) Use mathematical induction or strong induction to prove that every integer amount of postage of six cents or more can be formed using 3-cent and 4-cent stamps. (a) Basic Step (multiple base cases if strong induction is used) (b) Inductive Step he inductive hypothesis (c) Write the proposition to be proved true P(k + 1) (d) Put all steps together to prove that P(n) is true for all n 2 6Explanation / Answer
We can rewrite the question more mathematically as follows:
Show that, for any n6, there exist numbers k,lN{0} such that
n=3*a+4*b
(This basically means that we need to make the given amount using non negative amounts of 4 and 5 cents).
(a) Basic step:
For n = 6 we can take two 3 cents and no 4 cents (a=2,b=0).
Hence, P(6) is true.
For n = 7 we can take one 3 and one 4 cent.
Hence, P(7) is true.
(b) Inductive Step
Assume that for some amount k8,(we already proved for 6 and 7 in (a)) we get
k = 3*a + 4*b
Therefore, P(k) is true.
(c) Inductive Proposition
We want to prove that for
k+1 = 3*a' + 4*b' where a,bN{0}.
(d)
Case 1: a1, then k = 3*a + 4*b (from (b)) and so,
k+1 = 3*a + 4*b + 1
= 3*(a-1) + 3 + 4*b + 1
= 3*(a-1) + 4 + 4*b
= 3*(a-1) + 4*(b+1)
Note that since a1, (a-1) 0.
Hence, we have k+1 = 3*(a-1) + 4*(b+1).
Case 2: a=0
k = 4*b
k+1 = 4*b + 1
Here, k8 hence b2
k+1 = 4*(b-2) + 8+1
= 4*(b-2) + 9
= 4*(b-2) + 3*a
Hence, we can have k+1 = 3*a + 4*(b-2).
P(k+1) is true.
We can assumed that P(k) is true and proved P(k+1) is true. Hence, proved.