Как быстро посчитать сумму

[sdfcsx]

$S(1)=\dfrac{f(n)}{n}$

$S(2)=\dfrac{f(n+1)}{n}+\dfrac{f(n)}{n+1}

$S(3)=\dfrac{f(n+2)}{n}+\dfrac{f(n+1)}{n+1}+\dfrac{f(n)}{n+2}$

$S(4)=\dfrac{f(n+3)}{n}+\dfrac{f(n+2)}{n+1}+\dfrac{f(n+1)}{n+2}+\dfrac{f(n)}{n+3}

$....

$S(k)=?$
$S(k+1)=?$

Может существует реккурентная формула?
Так как это свёртка, если надо сразу и много - скажем S(10000), можно через преобразование Фурье просуммировать.
А мне надо быстро получать новое значение на каждом шаге. За время O(1).

[kotenok gav]

Определим $S(k,m)$ как $\sum\limits_{p=0}^{k-1}\frac{f(n+p)}{n+k-p-m-1}$ ($S(k)=S(k,0)$).
Тогда $S(k+1,m)=\frac{f(n+k)}{n+m}+S(k,m+1)$ (в частности, $S(k+1)=\frac{f(n+k)}n+S(k,1)$).

-- 27 апр 2020, 18:34 --

Кстати, интересный вопрос о $\lim\limits_{k\to\infty}S(k,m)$.

[arseniiv]

Выглядит безнадёжно. Одни и те же $S(m)$ и $f(n+m-1)$ (и любое заранее фиксированное количество свежих отсчётов) могут дать разные $S(n+1)$. Что-то приближённое получать тоже надежды не видно, так как последовательность $\frac1n$ неограниченна и влияние хвоста если и можно учесть как следует, то это не совсем тривиально.

[Vince Diesel]

А в каких пределах $n$? Сделать таблицу БПФ заранее для всех нужных отрезков $f(n)$ и ${1/n}$ не вариант?