Sum of the series formula 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)).
 A: 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.
A: 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.
