3. A particular store sells soda in packs of 5 cans and 7 cans. You can only buy

Question

3. A particular store sells soda in packs of 5 cans and 7 cans. You can only buy natural number packs of each type (you cannot split a pack). (a) What is the smallest value of n for which we can always buy exactly n or more cans of soda? For example, if you believe it is anything of 5 cans or more, write "5 cans or more." (that isnt the correct answer). (b) Prove your answer using weak induction. (c) Prove your answer using strong induction. Aside: You may wish to write a function that takes an integer parameter and outputs either how many of each type to purchase, using recursion based on your answer in this part. You don't have to turn in this for credit, but it may help you see the relationship between induction and recursion. (d) Explain briefly (1-2 sentences) how your inductive hypothesis differs in the previous two parts.

Explanation / Answer

if m and n are co-prime then the maximum number which is possible with combination is m*n -m-n

here m = 5 , n = 7,

hence 5*7 -5-7 = 35 -12 = 23

hence we can always buy 24 or more cans of soda

c)

Let P( n) be the statement that n cans
can be formed using just 5-can and 7-can soda. The parts of this
exercise outline a strong induction proof that P( n) is true for n 24
(a) we will show that the statements P(14), P(15), and P(16) are true, completing the basis step of the proof

24 = 5+5+7+7 , 25 = 5+ 5+5+5+5 , 26 = 5+ 7+7+7, 27= 5+ 5+5+5+7   , 28 = 7+7+7+7

so P(24), P(25), P(26), P(27), and P(28) are true

b) The inductive hypothesis is that P( n) is true for 24 n k where k 28. (Notice that this is a strong induction proof, which requires a stronger hypothesis.)

c) we will prove in the inductive step that P( k + 1) is true.

d) If k 28 , then k + 1 = (k 4) + 5. Since k – 4 24, by the
induction hypothesis we have that P(k 4) is true, i.e., k 2 cans can be purchased by using 5-can and 7- can soda.

Adding one 5-can soda , we can purchase k + 1 cans , i.e ., P( k +1) is true.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.