A problem of combinatorics (reduced from a problem of computing probability generating function)

Question

This is a problem involving computation of probability generating function (PGF).

I have reduced the problem into a problem of combinatorics, as given below. Let $f(n,k)$ be defined as

$$f(n+1,k):=f(n,k)+f(n,k-1)+\cdots+f(n,k-n)$$

where $f(n,k)=0$ for $k<0$, $f(1,0)=1$ and $f(1,k)=0$ otherwise. To show that

$$\sum_{k=0}^{\infty}s^k f(n,k)=\prod_{k=2}^n \frac{1-s^k}{1-s},\,\, |s|<1$$

Source : Rohatgi, Saleh. p.92. Problem 11. Thanks in advance.

Answer 1

You can solve this using induction; the base case $n = 1$ follows trivially by definition of $f(1,k)$ as given in the question.

We assume that the statement is true for a given value of $n$

$$\sum_{k=0}^\infty s^k f(n,k) = \sum_{k=-\infty}^\infty s^k f(n,k) = \prod_{m = 1}^n \frac{1 - s^m}{1-s}.$$

Note that the formula you give for $f(n+1,k)$ can be written as

$$f(n+1,k) = \sum_{j=0}^{n} f(n,k-j).$$

Now using the above

\begin{align*} \sum_{k=-\infty}^\infty s^k f(n+1,k) & = \sum_{k=-\infty}^\infty s^k \sum_{j = 0}^{n} f(n,k - j ) \\ & = \sum_{j=0}^{n} \sum_{k=-\infty}^\infty s^k f(n,k-j) \\ & = \sum_{j=0}^{n} s^{j} \sum_{k=\infty}^\infty s^{k -j} f(n,k-j) \\ & = \sum_{j=0}^{n} s^j \left( \prod_{m=1}^n \frac{1-s^m}{1-s} \right)\\ & = \left( \prod_{m=1}^n \frac{1-s^m}{1-s} \right) \left( \sum_{j=0}^{n} s^j \right) \\ & = \prod_{m=1}^{n+1} \frac{1-s^m}{1-s}. \end{align*}

A few notes to clarify some of the steps:

Although unncessary, I have used the convention of summing from $k = -\infty$ to $\infty$, rather than $k= 0$ as in the question. This is really just to make the point that we don't have to worry that shifting the series might lead to un-defined series entries; we know $f(n,k) = 0$ for $k \leq 0$ so this is ultimately not important.

In the second line we change the order of summation; this is possible because the terms in the series are all positive (you may feel you want to prove this to yourself).

Going between the fourth and fifth line, I am using the fact that the product is independent of $j$ to bring the product terms outside the summation.

Finally to get from the fifth to sixth lines I use the identity

$$\sum_{j=0}^n s^j = \frac{1 - s^{n+1}}{1-s}, \qquad |s| < 1.$$

Answer 2

The problem can be rewritten as $$ \left\{ \matrix{ f(n,k) = \sum\limits_{0\, \le \,j\, \le \,n - 1} {f(n - 1,k - j)} \hfill \cr f(n,k) = 0\quad \left| {\,n,k < 0} \right. \hfill \cr f(0,k) = f(1,k) = \left[ {0 = k} \right] \hfill \cr} \right. $$ and more compactly as $$ f(n,k) = \sum\limits_{0\, \le \,j\, \le \,n - 1} {f(n - 1,k - j)} + \left[ {0 = n} \right]\left[ {0 = k} \right] $$ where $[P]$ denotes the Iverson bracket $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$

Then let's take the generating function on the index $k$ $$ \eqalign{ & F(n,x) = \sum\limits_{0\, \le \,k} {f(n,k)\,x^{\,k} } = \sum\limits_{0\, \le \,j\, \le \,n - 1} {\sum\limits_{0\, \le \,k} {f(n - 1,k - j)\,x^{\,k} } } + \left[ {0 = n} \right] = \cr & = \sum\limits_{0\, \le \,j\, \le \,n - 1} {x^{\,j} \sum\limits_{0\, \le \,k} {f(n - 1,k - j)\,x^{\,k - j} } } + \left[ {0 = n} \right] = \cr & = {{1 - x^{\,n} } \over {1 - x}}F(n - 1,x) + \left[ {0 = n} \right] \cr} $$

Thus $$ \eqalign{ & F(0,x) = 1 \cr & F(1,x) = {{1 - x^{\,1} } \over {1 - x}} = 1 \cr & F(2,x) = {{1 - x^{\,2} } \over {1 - x}} = {{1 - x^{\,2} } \over {1 - x}}{{1 - x^{\,1} } \over {1 - x}} \cr & \quad \quad \vdots \cr & F(n,x) = \sum\limits_{0\, \le \,k} {f(n,k)\,x^{\,k} } = \prod\limits_{1\, \le \,\,k\, \le \,n} {{{1 - x^{\,k} } \over {1 - x}}} \cr} $$

$f(n,k)$ is OEIS sequence A008302.