\( a_{n+1} = 3 a_n + \bigant { a_n \sqrt 5 } \)

(*) Если целочисленная последовательность определяется формулой с антье (рекуррентной или формулой \( n \)-го члена), то можно получить достаточно неожиданный, а то и вовсе удивительный результат.
Например, оказывается, что числа Фибоначчи вычисляются по формуле \(
F_n = \ant { \frac { \varphi^n } {\sqrt 5} + \frac 12 }
\), где \(
\varphi = \frac {1 + \sqrt5} 2
\) — «золотое сечение» (число Фидия), хотя никакого намека на такие математические выкрутасы нет в определении чисел Фибоначчи (напомним, что \( F_1 = 1 \), \( F_2 = 1 \), далее при \(
n \in \mathbb N
\) \(
F_{n+2} = F_{n+1} + F_n
\)).
Одна из таких последовательностей встретилась в задаче на олимпиаде The 68th William Lowell Putnam Mathematical Competition (2007 год, см. архив задач).

68. Числовая последовательность \(
\bigl\{
1,\ 5, \ 26, \ 136, \ 712, \ \ldots
\bigr\}
\) задается рекуррентным способом: \[
a_1 = 1,
\quad
a_{n+1} = 3 a_n + \bigant { a_n \sqrt 5 }
\ \mbox { при } n \in \mathbb N.
\tag {68.1}
\] Выведите формулу \( n \)-го члена последовательности.
(Формулировка задачи изменена. В оригинале требуется найти \(
a_{2007} \).)

Решение. Заметим, что в задании последовательности \(
\bigl\{ a_n \bigr\}
\) встречается число \(
3 + \sqrt 5 = 2 \varphi^2 = 2 (\varphi + 1)
\) \[
a_{n+1} = \bigant { a_n ( 3 + \sqrt 5 ) } =
\bigant { 2 \varphi^2 a_n } .
\tag {68.1а}
\] Если у вас закрались подозрения, что тут будут задействованы числа Фибоначчи, то интуиция вас не подвела!
Еще, зададимся вопросом. В условии задачи приводятся пять первых членов последовательности. Зачем? Не исключено, что нам намекают поискать закономерность, которая может иметь место при вычислении первых членов последовательности \( \bigl\{ a_n \bigr\} \).
(Намеки, намеки — прямо как в «Алхимике» Пауло Коэльо.)
Попробуем: \[
a_2 = 5 = F_5,
\] \[
a_3 = 2 \cdot 13 = 2 F_7 , \] \[
a_4 = 4 \cdot 34  = 4 F_9 .
\] Предположим, что \[
a_n = 2^{n-2} F_{2n+1}
\ \mbox { при }
n \in \mathbb N .
\tag {68.2}
\] Несложно убедиться, \(
a_1 = \frac 12 \cdot 2  = \frac 12 F_3
\), \(
a_5 = 8 \cdot 89  = 8 F_{11} .
\)
Но формулу (68.2) еще предстоит доказать для любого натурального \( n \).

Рекуррентная формула (68.1) имеет двойника — другую рекуррентную формулу, но уже без антье. Ничего неожиданного, в (68.2) присутствуют числа Фибоначчи. \[
a_{n+1} =
3 a_n + \bigant { a_n \sqrt 5 } =
6 a_n + \bigant { - a_n (3 - \sqrt 5) } =
\] \[
=
6 a_n + \ant { - \dfrac {2 a_n} {\varphi^2} } =
6 a_n + \ant { - \dfrac {2 \ant {2 \varphi^2 a_{n-1}}} {\varphi^2} } =
\] \[
=
6 a_n + \ant {
- \dfrac {
4 \varphi^2 a_{n-1} - 2 \mant {2 \varphi^2 a_{n-1}}
} {\varphi^2}
} =
\] \[
=
6 a_n - 4 a_{n-1} + \ant {
\dfrac {
2 \mant {2 \varphi^2 a_{n-1}}
} {\varphi^2}
} =
6 a_n - 4 a_{n-1} ,
\] поскольку под знаком антье стоит положительное выражение, меньшее \( 1 \).
Таким образом, \[
a_{n+1} =
6 a_n - 4 a_{n-1} .
\tag {68.3}
\] Доказательство формулы (68.2) с помощью формулы (68.3) методом математической индукции предлагается провести самостоятельно.

Ответ: \(
a_n = 2^{n-2} \ant { \dfrac { \varphi^{2n+1} } {\sqrt 5} + \dfrac 12 }
\), где \(
\varphi = \dfrac {1 + \sqrt5} 2
\), \(
n \in \mathbb N \).