# Sequences and Series: Fibonacci and related numbers

## 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.

## Applications of Fibonacci and Related Numbers

- 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.