The sequence of Fibonacci numbers is defined as follows V 1

The sequence of Fibonacci numbers is defined as follows: ,V| = 1, x2 = 1, and, for n > 2, x = x_i plusa x_2. Prove thatfor every natural number n.[Hint: Use the fact that x = lplus 2^ and x = both satisfy 1 plus x = x2.]

Solution

We can solve the problem using the mathematical induction conept

Let n = 1

x1 = 1/sqrt(5) * [ 1/2 + sqrt(5)/2 - 1/2 + sqrt(5)/2]

x1 = 1/sqrt(5) * [sqrt(5)] = 1

Let us assume the given thing is true for n=k

xk = 1/sqrt(5) * [ (1/2 + sqrt(5)/2)^k - (1/2 + sqrt(5)/2)^k]

now we need to prove that the given thing hold true for (n=k+1)

x(k+1) = 1/sqrt(5) * [ (1/2 + sqrt(5)/2)^(k+1) - (1/2 + sqrt(5)/2)^(k+1)]

xk + x(k-1)

hence the given function is true for n=k+1

using the principle

x^2 = x + 1 then Phi^n = fib(n) Phi + fib(n-1)

(-Phi)^n = fib(n) (-Phi) + fib(n-1)

Phi^n - (-Phi)^n = fib(n)[Phi - (-Phi)]

fib(n) = [Phi^n - (-Phi)^n]/sqrt(5)