Editing Recurrence relation (section)

===Fibonacci numbers===
The recurrence of order two satisfied by the [[Fibonacci number]]s is the canonical example of a homogeneous [[linear recurrence]] relation with constant coefficients (see below).  The Fibonacci sequence is defined using the recurrence

:<math>F_n = F_{n-1}+F_{n-2}</math>

with [[initial condition]]s

:<math>F_0 = 0</math>
:<math>F_1 = 1.</math>

Explicitly, the recurrence yields the equations
:<math>F_2 = F_1 + F_0</math>
:<math>F_3 = F_2 + F_1</math>
:<math>F_4 = F_3 + F_2</math>
etc.

We obtain the sequence of Fibonacci numbers, which begins
:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

The recurrence can be solved by methods described below yielding [[Binet's formula]], which involves powers of the two roots of the characteristic polynomial <math>t^2 = t + 1</math>; the [[generating function]] of the sequence is the [[rational function]]
:  <math>\frac{t}{1-t-t^2}.</math>