On my discrete math lecture there was a fact that:
$\frac{1}{(1-x)^k}$ is a generating function for $a_n=\binom{n-k-1}{k-1}$
I'm interested in combinatorial proof of this fact. Is there any simple proof of such kind available somewhere? (I saw proof using $k$ x $n$ board where we're thinking of $n-k-1$ roads availible to point $(k,n)$ where we're choosisng $k-1$ fields to go right but I didn't understand it - is there a simpler proof somewhere?)
On
Suppose we have a sequence of values of length $k$ where the values are any non-negative integer. This is has the combinatorial specification $$\mathfrak{S}_{=k}\left(\sum_{q\ge 0} \mathcal{Z}^q\right).$$ This gives the generating function $$\frac{1}{(1-z)^k}.$$ On the other hand all such sequences can be obtained by stars-and-bars combining $n$ elements with $k-1$ dividers, giving $$\sum_{n\ge 0} {n+k-1\choose k-1} z^n,$$ which was to be shown.
It is quite easy to show by induction (or through other combinatorial arguments) that: $$ \sum_{n=0}^{N}\binom{n+k-1}{k-1}=\binom{N+k}{k},$$ hence if $$ f_k(x) = \sum_{n\geq 0}\binom{n+k-1}{k-1}x^n $$ it follows that $$ f_{k+1}(x) = \frac{f_k(x)}{1-x}=\frac{1}{(1-x)^{k+1}},$$ since if $$ f(z) = \sum_{n\geq 0} a_n z^n $$ we have: $$ \frac{f(z)}{1-z}=f(z)\sum_{n\geq 0}z^n = \sum_{n\geq 0} A_n z^n $$ where $A_n = \sum_{m=0}^{n} a_m.$