is it possible to find a closed expression to this?

Question

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?

Answer 1

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.