# Sequences and Series: Fibonacci and related numbers

## Understanding Fibonacci Sequence

• The Fibonacci sequence is a prominent example of a recurrence relation. It is defined as `f(0) = 0`, `f(1) = 1`, and `f(n) = f(n-1) + f(n-2)` for n > 1.
• Each term in the Fibonacci sequence is the sum of the two preceding ones, starting from 0 and 1.
• The Fibonacci sequence is named after Italian mathematician Leonardo of Pisa, also known as Fibonacci.

## Fibonacci and Golden Ratio

• The golden ratio, often symbolised by the Greek letter phi (Φ), is intimately associated with the Fibonacci sequence.
• As the Fibonacci sequence progresses, the ratio of consecutive terms increasingly approximates the golden ratio.
• The golden ratio, (1 + sqrt(5))/2, is approximately 1.61803398875. It is an irrational number.

## Binet’s formula

• The nth Fibonacci number can be expressed in a closed form using Binet’s formula: `f(n) = (Φ^n - (-Φ)^-n) / sqrt(5)`.
• Remember that in Binet’s formula, `Φ` is the golden ratio and `sqrt(5)` is the square root of 5.

## Pell Numbers

• In addition to the Fibonacci sequence, there are many other similar sequences with different initial conditions or recurrence relations.
• One of such sequences is the Pell numbers or Pell’s sequence. It is defined as `p(0) = 0`, `p(1) = 1`, and `p(n) = 2*p(n-1) + p(n-2)` for n > 1.

## Lucas Numbers

• Another similar sequence is the Lucas numbers. This sequence is defined as `l(0) = 2`, `l(1) = 1`, and `l(n) = l(n-1) + l(n-2)` for n > 1.
• The Lucas numbers have similar properties to the Fibonacci sequence but the initial values are different.
• The Fibonacci sequence and other sequences with similar recurrence relations can be seen in numerous areas including computer algorithms, counting problems, and biological modelling.
• The Fibonacci sequence also has interesting relationships with continued fractions, fractals, and Euclidean algorithm.
• The golden ratio, associated with the Fibonacci sequence, has many surprising appearances in art, architecture, and nature.