The Fibonacci numbers are the numbers 1,1,2,3,5,8,13,21,34... where the first two numbers are 1 and 1, and each number after that is the sum of the two previous numbers. (So 2 = 1+1, 3 = 2+1, and so on.)
Write an algorithm, in English, that takes a positive integer n as input and then outputs the nth Fibonacci number. For example, if we input to the algorithm n=2, your algorithm should output 1. If we input n=6, your algorithm should output 8.
Remember that an algorithm should consist of a series of unambiguous steps.
Use variable names to identify what values you are referring to. You can assume that the computer can do basic arithmetic.
Above, we have given two input-output examples. Be sure to test your algorithm to see if it can successfully reproduce these examples and any others you care to test.
There is a "formula" for finding the nth Fibonacci number
Fib (n) = Phi^n - (-phi)^n
Where Phi = 1 + sqrt (5) and phi = sqrt (5) -1