question 2 Part l: Strong Induction (50 pt.) (40 pt., 20/10 pt. each) Prove each

Question

question 2

Part l: Strong Induction (50 pt.) (40 pt., 20/10 pt. each) Prove each of the following statements using strong induction. For each statement, answer the following questions a. (4/2 pt.) Complete the basis step of the proof by showing that the base cases are true. b. (4/2 pt.) What is the inductive hypothesis? c. (4/2 pt.) What do you need to show in the inductive step of the proof? d. (8/4 pt.) Complete the inductive step of the proof. (20 pt.) Let al, a2,a3, 1. be the sequence defined by the following recurrence relation: A1-3, a,-5 ??3.ai-1-2.ai-2 for 12 3 Prove that an-2 +1 for any positive integer n. 2. (20 pt.) Let bo.bi, b2. be the sequence defined by the following recurrence relation: bo-5, b 16 b-7 bi-1 -10 b-2 for 22 Prove that bn 3 2" + 2 5" for any nonnegative integer n.

Explanation / Answer

2. a. Basis step

b0 = 3. 20 + 2.50 = 5 which is true.

b1 = 3.2+ 2.5 = 16 which is also true.

b. Inductive hypothesis:

We assume that for some integer k,

bk = 3. 2k + 2. 5k

c. We need to prove that whenever P(k) is true, P(k+1) is true for some variable k.

i.e bk+1 = 3. 2k+1 + 2. 5k+1 is true.

d. bk+1 = 7bk -10 bk-1

= 7.( 3. 2k + 2. 5k) - 10 ( 3. 2k-1 + 2. 5k-1)

= 21.2k+ 14.5k - 30.2k-1 - 20.5k-1

= 2k(21- 15) + 5k(14-4)

= 3.2k+1 +2.5k+1

So, whenever bk is true, bk+1 is also true.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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