is it possible to find a closed expression to this? let $f:\mathbb{N}^*\times\mathbb{N}\to\mathbb{N}$ a sequence defined by
$$f_n(m)=\begin{cases}1&n=1\\\displaystyle\sum_{i=0}^{m}f_{n-1}(i)&n>1\end{cases}$$
is it possible to define it without using recurrence?
Attempt:
I tried to calculate it for some $n$ to see if I could see a pattern
$$f_2(m)=\sum_{i=0}^{m}f_1(i)=\sum_{i=0}^{m}1=m+1\\
f_3(m)=\sum_{i=0}^{m}f_2(i)=\sum_{i=0}^{m}(i+1)=\frac{(m+1)(m+2)}{2}\\
f_4(m)=\sum_{i=0}^{m}f_3(i)=\sum_{i=0}^{m}\frac{(i+1)(i+2)}{2}=\frac{(m+1)(m+2)(m+3)}{6}$$
so I came with
$$f_n(m)=\frac{(m+n-1)!}{m!(n-1)!}$$
then I tried to prove with induction
$$n=1\Rightarrow f_1(m)=\frac{(m+1-1)!}{m!(1-1)!}=\frac{m!}{m!0!}=1\\
n=2\Rightarrow f_2(m)=\frac{(m+2-1)!}{m!(2-1)!}=\frac{(m+1)!}{m!1!}=m+1$$
assuming it holded for $n$, tried to prove to $n+1$
$$f_{n+1}(m)=\sum_{i=0}^{m}f_n(i)=\sum_{i=0}^{m}\frac{(i+n-1)!}{i!(n-1)!}=\frac{1}{(n-1)!}\sum_{i=0}^{m}\frac{(i+n-1)!}{i!}$$
but I don't know how to finish that proof, so.


*

*how can I finish that induction proof?

*is there a more easy way to approach that question/result?

 A: To finish that argument? We're trying to show that $\binom{m+n}{n} = \sum_{i=0}^{m}\binom{i+n-1}{n-1}$. This is known as the hockey stick identity. We normally prove it using the Pascal's triangle identity $\binom{i+n}{n}=\binom{i+n-1}{n-1}+\binom{i+n-n}{n}$ and another round of induction.
For another way, I'll demonstrate one of the most useful techniques for dealing with recurrences like this: generating functions.
Define $g_n(x) = \sum_{m} f_n(m)x^m$. The recurrence becomes
\begin{align*}f_n(m)x^m &= \sum_{i=0}^m f_{n-1}(i)x^i\cdot x^{m-i}\\
\sum_{m=0}^{\infty}f_n(m)x^m &= \sum_{m=0}^{\infty}\sum_{i=0}^m f_{n-1}(i)x^i\cdot x^{m-i}\\ \sum_{m=0}^{\infty}f_n(m)x^m &= \sum_{i=0}^{\infty} f_{n-1}(i)x^i\sum_{m=i}^{\infty}x^{m-i}\\ g_n(x) &= \sum_{i=0}^{\infty} f_{n-1}(i)x^i\cdot \frac{1}{1-x}= \frac{g_{n-1}(x)}{1-x}
\end{align*}
With $g_1(x)=\frac1{1-x}$, this gives us $g_n(x) = (1-x)^{-n}$. Now, what are the $f_n(m)$? Well, we have another way of finding a power series for $g_n$: the Taylor series $g_n(x) = \sum_{m=0}^{\infty} \frac1{m!}g_n^{(m)}(0)x^m$. The two series must agree, so
\begin{align*}f_n(m) &= \frac1{m!}g_n^{(m)}(0) = \left.\frac{n(n+1)\cdots (n+m-1)}{m!}(1-x)^{n-m}\right|_{x=0}\\
&= \frac{(n+m-1)!}{m!(n-1)!} = \binom{n+m-1}{n-1}\end{align*}
We have derived the coefficients without having to guess at anything.
