Can anyone give me a step by step on how to solve Strong Induction problems? If

Question

Can anyone give me a step by step on how to solve Strong Induction problems? If you could come up with a simple question and explain it to me I would be so thankful.

Honestly, this is the chapter that I REALLY don't understand and I'm thinking to skip it in exam.
Unless someone can help me with it here on Chegg/Cram

I will be rating fairly based on the best explanation.

Thanks!

Explanation / Answer

==> In strong induction the proof of the property for n+1 depends on the fact that it holds for all numbers 1, 2, ..., n ==> With strong induction, then, it is often necessary to prove multiple base cases. EXAMPLE: Every positive integer greater than 29 can be written as a sum of a non-negative multiple of 8 and a non-negative multiple of 5. 29= 3*8 +1*5 30 = 0*8 + 6*5 31 = 2*8 + 3*5 32 = 4*8 + 0*5 33 = 1*8 + 5*5 34 = 3*8 + 2*5 35 = 0*8 + 7*5 .. . . . ==>For an induction proof, we look for a pattern, but none seems apparent above. However, if we focus on the numbers themselves 29, 30, 31, ... We notice that, if n >= 34, then n-5 >= 29; thus, our strong induction hypothesis (namely that all integers 29, 30, ..., n-1 can be written in the desired form) ==> n-5 can be written in the form a*8 + b*5. But then we have n = (a*8 + b*5) + 5 = a*8 + (b+1)*5 ==>We showed above that the property holds for 29, 30, 31, 32, 33, and our written argument above shows that, for n >= 34, if the property holds for n-5, then it holds for n. By strong induction, the desired claim follows. Notice also that the property holds for 28 = 1*8 + 4*5, but it does NOT hold for 27.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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