Задача №18571

Найдите $a_{100}\text{,}$ если $a_1=1\text{,}$ $a_2=2\text{,}$ $a_3=23$ и для всех $n$ верно равенство:

$$a_{n+3}=3a_{n+2}-3a_{n+1}+a_n$$

Идея решения

Соотношение

$$a_{n+3}=3a_{n+2}-3a_{n+1}+a_n$$

— это линейная рекуррента третьего порядка с постоянными коэффициентами. Её характеристическое уравнение получается подстановкой $a_n=x^n\text{:}$

$$x^3=3x^2-3x+1⟺x^3-3x^2+3x-1=0.$$

Левая часть — это в точности разложение куба разности:

$$x^3-3x^2+3x-1=(x-1{)}^3=0.$$

Значит, $x=1$ — корень кратности $3\text{.}$

Общий вид последовательности

Если характеристическое уравнение имеет корень $x=1$ кратности $3\text{,}$ то общее решение рекурренты — это произвольный многочлен степени не выше второй от номера $n\text{:}$

$$a_n=A+Bn+C{n}^2,$$

где $A,B,C$ — постоянные (это стандартный факт для кратного корня: базис решений $1^n,n\cdot 1^n,n^2\cdot 1^n$).

Проверим, что такая формула действительно удовлетворяет рекурренте. Для многочлена $a_n=A+Bn+C{n}^2$ третья конечная разность тождественно равна нулю, а рекуррента как раз и означает зануление третьей разности:

$$a_{n+3}-3a_{n+2}+3a_{n+1}-a_n={\Delta }^3{a}_n=0,$$

что для многочлена степени $\le 2$ выполнено при всех $n\text{.}$ Значит, семейство $a_n=A+Bn+C{n}^2$ — это в точности все решения, и остаётся подобрать константы под начальные условия.

Нахождение коэффициентов

Подставляем $n=1,2,3$ и используем $a_1=1,a_2=2,a_3=23\text{:}$

$$\{\begin{array}{l}A+B+C=1,\\ A+2B+4C=2,\\ A+3B+9C=23.\end{array}$$

Вычтем из второго уравнения первое, а из третьего — второе:

$$B+3C=1,B+5C=21.$$

Вычитая, получаем $2C=20\text{,}$ то есть $C=10\text{.}$ Тогда $B=1-3\cdot 10=-29\text{,}$ и наконец $A=1-B-C=1+29-10=20\text{.}$

Итак,

$$a_n=10n^2-29n+20.$$

Контроль по начальным данным:

Все три условия выполнены.

Вычисление $a_{100}$

$$a_{100}=10\cdot 100^2-29\cdot 100+20=100000-2900+20=97120.$$

Для надёжности этот же результат получен прямым разгоном рекурренты от $a_1,a_2,a_3$ до $a_{100}\text{:}$ он совпал со значением по формуле.

Ответ

$$a_{100}=97120.$$