Sum of the series formula

Question

I need to figure out the sum of the series as quickly as possible in a program given n and k: $$f(n,k)= \frac{\sum_{i=0}^{n-1}f(i,k-1)}{n} $$ and $ f(i,0) =i $ for all $i$.

I did some paper work and brought the solution to $$f(n,k)=\frac{f(n-1,k-1)}{n} + \frac{(n-1)f(n-1,k)}{n} $$ But I need a closed form solution. Is it possible to give results in O(1) or O( lg n) time (preprocessing is allowed but should not be of the order of O(n^2 ) or O( k^2)).

Answer 1

This solution is wrong.

$$f(n,1) = \dfrac{\sum_{i=0}^{n-1} f(i,0)}n = \dfrac{\sum_{i=0}^{n-1} i}n = \dfrac{n(n-1)}{2n} = \dfrac{n-1}2$$ $$f(n,2) = \dfrac{\sum_{i=0}^{n-1} f(i,1)}n = \dfrac{\sum_{i=0}^{n-1} (i-1)}{2n} = \dfrac{n(n-1)/2 - n}{2n} = \dfrac{(n-1)/2-1}2 = \dfrac{n-3}4$$ $$f(n,3) = \dfrac{\sum_{i=0}^{n-1} f(i,2)}n = \dfrac{\sum_{i=0}^{n-1} (i-3)}{4n} = \dfrac{n(n-1)/2 - 3n}{4n} = \dfrac{(n-1)/2-3}4 = \dfrac{n-7}8$$ Hence, in general, we can guess $$f(n,k) = \dfrac{n-(2^k-1)}{2^k} = -1 + \dfrac{n+1}{2^k}$$ Once we have this prove that our guess is indeed true by induction.

Answer 2

The solution by Marvis would be really nice if it worked, but the formula for $f(n,1)$ fails when $n=0$, and this propagates to subsequent computation. By the way: although this is implicit in the recursive formula, it would help to specify $f(0,k)=0$ explicitly in the statement of the problem.

Let's consider only $n\ge 1$ from now on. Then $f(n,1) = \frac12(n-1)$ holds, and $$f(n,2) = \frac{1}{2n} \sum_{i=1}^{n-1}(i-1) =\frac{1}{2n} \left\{\frac{n(n-1)}{2}-n+1\right\} = \frac{n-3}{4} +\frac{1}{2n} \tag1$$ Using the notation $H_n=1+\frac12+\dots+\frac1{n}$ for harmonic numbers, we find $$\begin{align}f(n,3) & = \frac{1}{4n} \sum_{i=1}^{n-1}(i-3) + \frac{1}{2n}\sum_{i=1}^{n-1} \frac{1}{i} = \frac{1}{4n} \left\{ \frac{n(n-1)}{2} -3n+3\right\}+\frac{H_{n-1}}{2n} \\ &= \frac{n-7}{8} +\frac{3}{4n}+\frac{H_{n-1}}{2n} \end{align} \tag2$$

This brings an unpleasant realization: if we could compute $f(n,3)$ in $O(1)$, then the same could be done for the harmonic numbers. I looked around for algorithms for computing $H_n$ and found this discussion. Did not read carefully, but maybe it can be optimized to $O(\lg n)$.

Moving forward, we encounter the sums of $H_{n-1}/n$. A superficially(?) similar concept is hyperharmonic numbers, defined by $H_n^{(1)}=H_n$ and $H_n^{(r)}=\sum_{i=1}^n H_n^{(r-1)}$ when $r\ge 2$. The formula by Conway and Guy (e.g., here) tells us that $r$ adds very little complexity: $$H_n^{(r)} = \binom{n+r-1}{r-1}(H_{n+r-1}-H_{r-1}) \tag3$$ Unfortunately, $n$ in the denominator of $H_{n-1}/n$ does not allow the hyperharmonic numbers to appear, as far as I can tell.
$$\begin{align}f(n,4) & = \frac{1}{8n} \sum_{i=1}^{n-1}(i-7) + \frac{3}{4n}H_{n-1} + \frac{1}{2n}\sum_{i=1}^{n-1}\frac{H_{i-1}}{i} \\ &= \frac{n-15}{16} +\frac{7}{8n} + \frac{3}{4n}H_{n-1} + \frac{1}{2n}\sum_{i=1}^{n-1}\frac{H_{i-1}}{i} \end{align} \tag4$$ In general, if we define $$H_n^{[r]}=\sum_{i=1}^{n-1}\frac{H_{i}^{[r-1]}}{i},\quad H_n^{[0]}=1 \tag5$$ then $$f(n,k) = \frac{n-(2^k-1)}{2^k} +\sum_{r=0}^{k-2} \frac{2^{k-r-1}-1}{2^{k-r-1}n}H_n^{[r]} \tag6$$ where the corrector terms $H_n^{[r]}$ get increasingly expensive to compute.