Explicit form for recurrence relation I am interested in a closed formula for this kind of sum. Let's assume $f$ is a function well-defined on $\mathbb{N}$. Let's define the following recurrence formula:
$\left\{ 
\begin{array}{c}
f_0(x) = f(x),\space x \in \mathbb{N}\\ 
f_{n+1}(x) = \sum_{i=1}^x {f_n(i)}
\end{array}
\right.$
Any ideas ?
 A: In fact, a double sequence is hidden behind your recurrence relation, because the functions $(f_n)_{n\in\mathbb{N}}$ form a sequence, each element of which contitutes itself, as function on integers, a sequence $(f_n(m))_{m\in\mathbb{N}}$. In consequence, let's denote this double sequence by $a_{nm}:=f_n(m)$; your problem is then restated as
$$
\begin{cases}
   \displaystyle a_{nm} = \sum_{k=1}^m a_{n-1,k} & \forall n,m \ge 1 \\
   \displaystyle a_{0,m} = f(m)                  & \forall m \ge 0
\end{cases}
$$
Here appears a first issue : there is no initial condition for the second index. As is, the problem is thus not well-posed. For that reason, let's add the following condition :
$$
a_{n,0} = g(n) \;\; \forall n \ge 1
$$
Now, even if this recurrence relation is quite hard to solve in the current form, since it is linear with respect to the elements of the sequence, it is possible to use its generating function, that is why one defines $\displaystyle A(x,y) := \sum_{n,m\ge0}a_{nm}x^ny^m$ (be careful that this $x$ is different from yours, this one a continuous variable). The solution of your problem will be then given by
$$
\displaystyle f_n(m) = a_{nm} = \frac{1}{n!m!}\left.\frac{\partial^{n+m}A}{\partial x^n \partial y^m}\right|_{x=0,y=0}
$$
One still has to find the generating function. Let's decompose $A(x,y)$ with the help of the recurrence relation :
$$
\begin{array}{rcll}
A(x,y)
   &=& \displaystyle
   \sum_{n,m\ge0} a_{nm} x^n y^m \\
   &=& \displaystyle
   a_{00} + \sum_{n\ge1}a_{n,0}x^n + \sum_{m\ge1}a_{0,m}y^m + \sum_{n,m\ge1}a_{nm}x^ny^m & (1) \\
   &=& \displaystyle
   f(0) + \sum_{n\ge1}g(n)x^n + \sum_{m\ge1}f(m)y^m + \sum_{n,m\ge1}\sum_{k=1}^ma_{n-1,k}x^ny^m & (2) \\
   &=& \displaystyle
   f(0) + \sum_{n\ge1}g(n)x^n + \sum_{m\ge1}f(m)y^m + x\sum_{n\ge0}\sum_{m\ge1}\sum_{k=1}^ma_{nk}x^ny^m & (3) \\
   &=& \displaystyle
   f(0) + \sum_{n\ge1}g(n)x^n + \sum_{m\ge1}f(m)y^m + x\sum_{n\ge0}\sum_{k\ge1}\sum_{m\ge k+1}a_{nk}x^ny^m & (4) \\
   &=& \displaystyle
   f(0) + \sum_{n\ge1}g(n)x^n + \sum_{m\ge1}f(m)y^m + \frac{xy}{1-y}\sum_{n\ge0}\sum_{k\ge1}a_{nk}x^ny^k & (5) \\
   &=& \displaystyle
   f(0) + \sum_{n\ge1}g(n)x^n + \sum_{m\ge1}f(m)y^m + \frac{xy}{1-y}\left(\sum_{n\ge0}\sum_{k\ge0}a_{nk}x^ny^k - \sum_{n\ge0}a_{n,0}x^n\right) & (6) \\
   &=& \displaystyle
   \left(1-\frac{xy}{1-y}\right)f(0) + \left(1-\frac{xy}{1-y}\right)\sum_{n\ge1}g(n)x^n + \sum_{m\ge1}f(m)y^m + \frac{xy}{1-y}A(x,y) & (7)
\end{array}
$$
hence
$$
A(x,y) = f(0) + \sum_{n\ge1}g(n)x^n + \frac{1-y}{1-y-xy}\sum_{m\ge1}f(m)y^m
$$
which cannot be simplified further without specifying $f$ and $g$.
Note that the steps of the previous derivation are : (1) extracting the initial conditions from the sums; (2) using the recurrence relation; (3) re-indexing $n$ from $0$; (4) switching the sums in $m$ and $k$; (5) summing on $m$, using the truncated geometric series $\sum_{m\ge k+1}y^m = \frac{y^{k+1}}{1-y}$; (6) re-indexing $k$ from $0$ and adjusting; (7) recollecting the differents terms and using the definition of $A(x,y)$.

Addendum
Another path is made of the following manipulations with nested sums :
$$
\begin{array}{rcll}
f_n(m) 
   &=& \displaystyle 
   \sum_{k=1}^m f_{n-1}(k) \\
   &=& \displaystyle 
   \sum_{k_1=1}^m\sum_{k_2=1}^{k_1} \cdots \sum_{k_n=1}^{k_{n-1}} f_0(k_n) & (1) \\
   &=& \displaystyle 
   \sum_{k_n=1}^m\sum_{k_{n-1}=k_n+1}^m \cdots \sum_{k_1=k_2+1}^m f(k_n) & (2) \\
   &=& \displaystyle 
   \sum_{k_n=1}^mf(k_n)\sum_{k_{n-1}=k_n+1}^m \cdots \sum_{k_2=k_3+1}^m (m-k_2) & (3) \\
   &=& \displaystyle 
   \sum_{k_n=1}^mf(k_n)\sum_{k_{n-1}=k_n+1}^m \cdots \sum_{k_3=k_4+1}^m \left((m-k_3) + \frac{1}{2}m(m+1) - \frac{1}{2}k_3(k_3+1)\right) & (4) \\
   &=& \displaystyle 
   \ldots \\
   &=& \displaystyle 
   \sum_{k=1}^m p_{n-1}(k)f(k) & (5)
\end{array}
$$
where $p_{n-1}(k)$ is a polynomial expression of degree $n-1$ in $m$ and $k$. The steps are : (1) using recurrence relation $n$ times; (2) switching all the sums; (3) summing on $k_1$; (4) summing on $k_2$; (5) sums of powers are polynomial.
