Let a, be the nth term of the sequence defined recursively by 1 an + 1 1 + an and a, = 1. Find a formula for a, in terms of the Fibonacci numbers Fp. an = Prove that the formula you found is valid for...

Extracted text: Let a, be the nth term of the sequence defined recursively by 1 an + 1 1 + an and a, = 1. Find a formula for a, in terms of the Fibonacci numbers Fp. an = Prove that the formula you found is valid for all natural numbers n. Let P(n) denote the statement that a, = = 1, which is true. P(1) is the statement that a, = Assume that P(k) is true. Thus, our induction hypothesis is ak = We want to use this to show that P(k + 1) is true. Now, 1 ak+1 = 1 + ak 1 1 + Thus, P(k + 1) follows from P(k), and this completes the induction step. Having proven the above steps, we conclude by the Principle of Mathematical Induction that P(n) is true for all n 2 1.