Use the PCI(principle of complete induction) to prove thefollowing prpperties of

Question

Use the PCI(principle of complete induction) to prove thefollowing prpperties of Fibonacci numbers: fn+6 = 4fn+3 +fn for allnatural numbers n. Use the PCI(principle of complete induction) to prove thefollowing prpperties of Fibonacci numbers: fn+6 = 4fn+3 +fn for allnatural numbers n.

Explanation / Answer

Fibonacci Sequence is defined by fn = fn-1 + fn-2 for n>2 andf1 = 0 , f2 = 1. Let k>2 then fk+6 = fk-1+6 + fk-2+6 Assume that the statement fn+6 = 4fn+3 +fn is true for n=k-1 and n=k-2 then fk+6 = 4fk-1+3 + fk-1 +4fk-2+3 +fk-2        = 4(fk-1+3 +fk-2+3) + (fk-1+fk-2)         = 4fk+3 +fk So its true for k if it is true for k-1 and k-2. So we need to show its true for n=1, n=2 The Fibonacci sequence is 0 1 1 2 3 5 8 13 For n=1, f7 = 8 , f4 = 2 ,f1 = 0 , 8 = 4x2 + 0 , so statement is true For n=2, f8 = 13, f5 = 3 , f2 = 1, 13 = 4x3 +1 , so statement is true That completes the proof.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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