Explore BrainMass

Solve Fibonacci recursion relation

Solve the recurrence relation

x_(n+1) = x_n + x_(n-1), x_0 = 1, x_1 = 1.

That it, find a formula for x_n in terms of n

Solution Preview

Solution analogous to Ordinary Differential Equation (ODE):

There is a "not-quite a typo" in initial conditions, which can lead to contradictions, as we shall see below.
Otherwise, the ODE works well, as follows.
We seek solution in an exponential form x =a^(n+k), where a and k are constants.
We shall find "a" from the ...