Вычисление без компьютера

[Руст]

Линейные рекурентные уравнения, как и линейные дифференциальные уравнения легко решается. Предлагаю вычислить:
$a_i=i,i\le k, a_n=(a_{n-1}+a_{n-2}+\dots+a_{n-k})/k,n>k$.
Вычислить $a_{2000000}$ при k=1000 с точностью до 1000 знаков после запятой.

[Руст]

Вообще то меня разочаровало, что народ не решает даже линейные уравнения.
Приведу решение и этой задачи с аналогией дифференциальных уравнений.
Рассмотрим вначале общее рекурентное уравнение:
$x_n=\sum_{i=1}^k b_I x_{n-i}$.
Оно решается аналогично дифференциальному уравнению:
$y^{(k)}=\sum_{i=1}^k b_i y^{(k-i)}$.
Решение первого ищется в виде комбинаций степеней, второго в виде комбинаций экспонент:
$x_n=\sum_i C_i s_i^{n-1}, y(t)=\sum_i C_i exp(s_i t).$
Характеристические числа и в том и в этом случае находятся как корни уравнения:
$f(s)=s^n-\sum_{i=1}^k b_i s^{k-i} =0$.
Здесь мы рассматриваем только случай отсутствия кратных корней (чему соответствует исходное уравнение). Сами коэффициенты перед степенями находятся так же, как и в случае дифференциального уравнения из соотношений:
$\sum_i C_is_i^j=x(j+1) \ (y^{(j)}(0) \ for \ diff. \ equat. \ ), j=0,1,\dots, k-1$.
Сложим все уравнения умножив j -ое уравнение на c(i,j) и получим:
$C_i f_i(s_i)=\sum_{j=0}^{k-1} c(i,j)x(j+1),f_i(s)=\frac{f(s)}{s-s_i}=\sum_{j=0}^kc(i,j)s^j$
Остается эти выкладки применить к исходной задаче. В этом случае характеристический многочлен получается:
$f(s)=ks^k-\frac{s^k-1}{s-1},s_0=1,f_0(s)=ks^{k-1}+(k-1)s^{k-2}+\dots+1$.
Это дает коэффициент перед постоянной 1:
$C_0=\frac{\sum_{j=1}^k j^2 }{\sum_{j=1}^k j}=\frac{2k+1}{3}.$
Остаётся оценить остальные члены. Они при больших k находятся по приближённой формуле:
$s_j=r_jexp(iq_j),r_j~exp(-t_j/k),q_j~2\pi j/(k-1),exp(2t_j)=(t_j+1)^2+4\pi ^2j^2,j=1,2,...,k-1$
При этом коэффициенты перед комплексными корнями получаются ограниченными и учитывая, что за k шагов оставшиеся добавки убывают более 8 раз, соответственно за 2k шагов заведомо больше 10 раз, можно их отбросить сохраняя точность в 1000 знаков при 2000k итерациях. Следовательно
$a_{2000k}=\frac{2k+1}{3}=667 \ (k=1000)$
с точностью до 1000 знаков.

[maxal]

Так уже обсуждали.