Арифметико-геометрическая прогрессия

Рекуррентные соотношения первого порядка, к которым относится арифметико-геометрическая прогрессия, изучались математиками с древних времён. Задачи на вычисление сложного процента и рост популяций по сути сводились к соотношению вида ${\displaystyle u_{n+1}=qu_{n}+d}$.

Систематическое изучение линейных рекуррентных последовательностей было оформлено в XVIII веке работами Абрахама де Муавра и Леонарда Эйлера в контексте решения разностных уравнений. Муавр в своей работе «Miscellanea Analytica» (1730) разработал метод производящих функций для решения рекуррентных соотношений, который применим и к АГП.

В отечественной математической литературе термин «арифметико-геометрическая прогрессия» для обозначения последовательности ${\displaystyle u_{n+1}=qu_{n}+d}$ получил распространение благодаря статье Я. Н. Суконника в журнале «Квант» (1975), где были подробно исследованы свойства такой последовательности и её связь с арифметическими и геометрическими прогрессиями^[1].

Следует отметить терминологическую особенность: в современной международной и вузовской литературе термин «арифметико-геометрическая прогрессия» (англ. arithmetico-geometric sequence) чаще применяется к последовательности вида ${\displaystyle u_{n}=(a+(n-1)d)q^{n-1}}$ (произведение членов арифметической и геометрической прогрессий).

Последовательность же, задаваемая рекуррентным соотношением ${\displaystyle u_{n+1}=qu_{n}+d}$, строго классифицируется как линейная рекуррентная последовательность первого порядка (или аффинная последовательность). Однако в ряде отечественных учебных и популярных изданий (в частности, в классической статье Я. Н. Суконника в журнале «Квант») за данной рекурсией исторически закрепилось название арифметико-геометрической прогрессии^[2][3].

• При ${\displaystyle q=1}$ арифметико-геометрическая прогрессия превращается в арифметическую прогрессию: ${\displaystyle u_{n}=u_{n-1}+d}$.
• При ${\displaystyle d=0}$ (и ${\displaystyle q\neq 0}$) она превращается в геометрическую прогрессию: ${\displaystyle u_{n}=q\cdot u_{n-1}}$.

• Арифметико-геометрическая прогрессия является линейной рекуррентной (возвратной) последовательностью второго порядка. Последовательность называется возвратной второго порядка, если каждый её член, начиная с некоторого номера, выражается как линейная комбинация двух предыдущих членов с постоянными коэффициентами: ${\displaystyle u_{n+1}=au_{n}+bu_{n-1}}$. Исключив параметр ${\displaystyle d}$ из двух соседних рекуррентных соотношений АГП (${\displaystyle u_{n+1}=qu_{n}+d}$ и ${\displaystyle u_{n}=qu_{n-1}+d}$), легко получить именно такую связь с коэффициентами ${\displaystyle a=q+1}$ и ${\displaystyle b=-q}$:

${\displaystyle u_{n+1}=(q+1)u_{n}-qu_{n-1}}$. Соответствующее характеристическое уравнение этой рекуррентной последовательности имеет вид ${\displaystyle \lambda ^{2}-(q+1)\lambda +q=0}$, его корни ${\displaystyle \lambda _{1}=q}$ и ${\displaystyle \lambda _{2}=1}$ напрямую определяют структуру общей формулы члена прогрессии.

• Критерий стационарности: прогрессия является стационарной (${\displaystyle u_{1}=u_{2}=u_{3}=\dots }$) тогда и только тогда, когда:
  • либо ${\displaystyle q=1}$ и ${\displaystyle d=0}$;
  • либо ${\displaystyle q\neq 1}$ и начальный член удовлетворяет условию ${\displaystyle u_{1}={\dfrac {d}{1-q}}}$.
• Предел последовательности: при ${\displaystyle |q|<1}$ последовательность всегда сходится, и её предел равен:

${\displaystyle \lim _{n\to \infty }u_{n}=\lim _{n\to \infty }\left[\left(u_{1}+{\frac {d}{q-1}}\right)q^{n-1}-{\frac {d}{q-1}}\right]={\frac {d}{1-q}}}$.

Рекуррентное соотношение арифметико-геометрической прогрессии может быть элегантно записано в матричном виде, что связывает эту тему с линейной алгеброй.

Введя вектор состояния ${\displaystyle V_{n}={\begin{pmatrix}u_{n}\\1\end{pmatrix}}}$, получим:

${\displaystyle {\begin{pmatrix}u_{n+1}\\1\end{pmatrix}}={\begin{pmatrix}q&d\\0&1\end{pmatrix}}{\begin{pmatrix}u_{n}\\1\end{pmatrix}}}$.

Отсюда ${\displaystyle n}$-й член прогрессии выражается через ${\displaystyle n}$-ю степень матрицы перехода:

${\displaystyle V_{n}=A^{n-1}V_{1}}$, где ${\displaystyle A={\begin{pmatrix}q&d\\0&1\end{pmatrix}}}$.

Диагонализация этой матрицы автоматически приводит к выводу формулы общего члена. Собственные значения матрицы ${\displaystyle A}$ равны ${\displaystyle \lambda _{1}=q}$ и ${\displaystyle \lambda _{2}=1}$, что соответствует двум компонентам решения: геометрической прогрессии (связанной с ${\displaystyle q}$) и постоянной составляющей (связанной с ${\displaystyle 1}$).

Поведение арифметико-геометрической прогрессии наглядно демонстрируется с помощью паутинной диаграммы (англ. cobweb plot или метод итераций), широко используемого в теории динамических систем.

На координатной плоскости строятся:

• график линейной функции ${\displaystyle f(x)=qx+d}$;
• биссектриса первого координатного угла ${\displaystyle y=x}$.

Точка их пересечения ${\displaystyle x^{*}={\frac {d}{1-q}}}$ является неподвижной точкой (стационарным значением) отображения.

Начиная с точки ${\displaystyle (u_{1},0)}$, строят «ступеньки»:

1. Вертикально до графика ${\displaystyle f(x)}$ (получаем точку ${\displaystyle (u_{1},u_{2})}$).
2. Горизонтально до прямой ${\displaystyle y=x}$ (получаем точку ${\displaystyle (u_{2},u_{2})}$).
3. Снова вертикально до графика ${\displaystyle f(x)}$ и так далее.

При ${\displaystyle |q|<1}$ эта «паутина» сходится к неподвижной точке (аттрактор), что геометрически иллюстрирует существование предела прогрессии. При ${\displaystyle |q|>1}$ последовательность расходится (репеллер), а при ${\displaystyle q=-1}$ возникают колебания между двумя значениями.

Постановка задачи. Даны три вертикальных стержня, на один из которых надеты ${\displaystyle n}$ дисков различного диаметра в виде пирамиды (внизу лежит диск наибольшего диаметра, вверху — наименьшего). За одно действие разрешается переместить один диск с любого стержня на любой другой, при этом нельзя класть больший диск на меньший. Какое наименьшее количество действий ${\displaystyle c_{n}}$ требуется, чтобы переместить всю пирамиду на другой стержень^[5][6][7]?

Вывод рекуррентного соотношения

Обозначим через ${\displaystyle c_{n}}$ искомое минимальное количество действий. В какой-то момент нам придётся перемещать самый большой (нижний) диск. Это можно сделать только в том случае, если все остальные ${\displaystyle n-1}$ дисков сложены в виде пирамиды на вспомогательном стержне. На такое перемещение требуется ${\displaystyle c_{n-1}}$ действий. Ещё одно действие (${\displaystyle 1}$) требуется для того, чтобы переместить сам нижний диск на целевой стержень. Наконец, оставшиеся ${\displaystyle n-1}$ дисков со вспомогательного стержня необходимо переместить на целевой стержень (на нижний диск). На это снова потребуется ${\displaystyle c_{n-1}}$ действий.

Следовательно, имеет место рекуррентное соотношение: ${\displaystyle c_{n}=2c_{n-1}+1}$ Ясно, что ${\displaystyle c_{1}=1}$, так как один диск перемещается за одно действие.

Арифметико-геометрическая прогрессия важна в финансовой математике для расчета будущей стоимости аннуитета (серии равных платежей)^[8].

Пусть:

• ${\displaystyle u_{n}}$ — сумма на счёте в конце ${\displaystyle n}$-го периода;
• ${\displaystyle q=1+r}$, где ${\displaystyle r}$ — процентная ставка за период;
• ${\displaystyle d}$ — регулярный взнос (положительный при пополнении, отрицательный при снятии средств).

Тогда баланс изменяется по закону:

${\displaystyle u_{n+1}=(1+r)u_{n}+d}$.

Используя формулу общего члена АГП, можно вывести классическую формулу сложных процентов с регулярными платежами:

${\displaystyle u_{n}=u_{1}(1+r)^{n-1}+d{\frac {(1+r)^{n-1}-1}{r}}}$.

Методы, применяемые к арифметико-геометрическим прогрессиям, часто используются для суммирования рядов вида ${\displaystyle \sum _{k=1}^{n}k\cdot q^{k}}$, что является примером «международного» понимания термина АГП^[9].

Пусть ${\displaystyle S=1\cdot q+2\cdot q^{2}+3\cdot q^{3}+\dots +n\cdot q^{n}}$.

Умножим на ${\displaystyle q}$:

${\displaystyle qS=1\cdot q^{2}+2\cdot q^{3}+\dots +(n-1)\cdot q^{n}+n\cdot q^{n+1}}$.

Вычитая второе из первого, получаем геометрическую прогрессию:

${\displaystyle S(1-q)=q+q^{2}+q^{3}+\dots +q^{n}-n\cdot q^{n+1}=q{\frac {1-q^{n}}{1-q}}-n\cdot q^{n+1}}$,

откуда:

${\displaystyle S={\frac {q(1-q^{n})}{(1-q)^{2}}}-{\frac {n\cdot q^{n+1}}{1-q}}}$.

Этот метод исторически и методологически тесно связан с теорией арифметико-геометрических прогрессий и демонстрирует универсальность подхода, основанного на умножении на знаменатель и вычитании.

Между любыми тремя членами АГП существует линейная зависимость, связывающая их значения и степени знаменателя ${\displaystyle q}$.

Доказательство следует из того, что векторы ${\displaystyle (1,1,1)}$, ${\displaystyle (q^{k},q^{l},q^{m})}$ и ${\displaystyle (u_{k},u_{l},u_{m})}$ линейно зависимы, поскольку ${\displaystyle u_{x}}$ линейно выражается через ${\displaystyle 1}$ и ${\displaystyle q^{x}}$.

• Последовательность частичных сумм ${\displaystyle S_{n}}$ членов АГП сама является линейной рекуррентной последовательностью третьего порядка и удовлетворяет соотношению: ${\displaystyle S_{n+1}=(q+2)S_{n}-(2q+1)S_{n-1}+qS_{n-2}}$^[10].
• Если последовательность частичных сумм ${\displaystyle S_{n}}$ сама образует арифметико-геометрическую прогрессию, то исходная последовательность ${\displaystyle u_{n}}$ является чисто геометрической прогрессией.
• АГП тесно связана с методом простых итераций для решения уравнений вида ${\displaystyle x=qx+d}$.