Последовательность Фибоначчи

Рассмотрим хорошо известную последовательность чисел Фибонначи:

$\displaystyle 0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 11,\ 19,\ldots$

Каждый член последовательности Фибоначчи равен сумме предыдущих членов, при этом задаются два первых члена: 0 и 1.

Поставим следующую задачу.

Найти n-ый член последовательности, так, чтобы в ответ входил только номер члена последовательности.

При решении этой задачи необходимо воспользоваться теорией решения разностных уравнений.

Запишем реккурентное соотношение на чоены последовательности:

$\displaystyle a_n=a_{n-1}+a_{n-2},$

где

- n-ый член последлвательности.

Получаем, что это есть разностное уравнение второго порядка с постоянными коэффициентами, которое решается в явном виде.

Поставим для этого разностного уравнения начальную задачу (задачу Коши). Учтем, что

$\displaystyle a_0=0,\qquad a_1=1.$

Решение разностного уравнения будем искать в следующем виде:

$\displaystyle a_n=q^n,$

где q - число.

Подставляя решение в исходное разностное уравнение, получаем:

$\displaystyle a_n=a_{n-1}+a_{n-2}$

$\displaystyle q^n=q^{n-1}+q^{n-2},$

здесь ищется ненулевое решение, поэтому представляется возможность сократить данное выражение:

$\displaystyle q^n=q^{n-1}+q^{n-2}$

$\displaystyle q^n-q^{n-1}-q^{n-2}=0$

$\displaystyle q^{n-1}(q^2-q-1)=0$

$\displaystyle q^2-q-1=0.$

Решая квадратное уравнение, получаем корни:

$\displaystyle q_{1,2}=\frac{1\pm\sqrt{5}}{2}.$

Тогда общее решение разностного уравнения записывается в следующем виде:

$\displaystyle a_n=Aq_1^n+Bq_2^n,$

где A и B - произвольные постоянные.

Постоянные находятся так, чтобы общее решение удовлетворяло начальным условиям:

$\displaystyle a_0=A+B=0\qquad a_1=Aq_1+Bq_2=1.$

Отсюда получаем, что

$\displaystyle A=\frac{1}{\sqrt{5}},\ B=-\frac{1}{\sqrt5}.$

Тогда решение записывается в следующем виде:

$\displaystyle a_n=\frac{1}{\sqrt{5}}(q_1^n-q_2^n)= \frac{1}{\sqrt{5}}(q_1^n-q_1^{-n})=$

$\displaystyle = \frac{1}{2^n\sqrt{5}} \left( (1+\sqrt{5})^n-(1-\sqrt{5})^n\right).$