I need some help in showing that in product among $n$ lower triangular matrices, the number of addends to be summed in order to obtain the value of the elements $(i, j)$ is: $\frac{<n>_{i-j}}{(i-j)!}$.
I made the conclusion that to obtain the value of the element $(i, j)$ in product of $n$ lower triangular matrices, I must have the value of all the elements with index $(i, k) : k \le i$ after products of $n-1$ matrices.
So I am saying: $\sum_{k=0}^{i-j} \frac{<n-1>_{k}}{k!} = \frac{<n>_{i-j}}{(i-j)!}$. I am trying to prove this statement with induction:
base step with $n=2$: $\sum_{k=0}^{i-j} \frac{<1>_{k}}{k!} = \sum_{k=0}^{i-j} 1 = i - j + 1 = \frac{<2>_{i-j}}{(i-j)!} =1$
induction step: hp $\sum_{k=0}^{i-j} \frac{<n-1>_{k}}{k!} = \frac{<n>_{i-j}}{(i-j)!}$ and th $\sum_{k=0}^{i-j} \frac{<n>_{k}}{k!} = \frac{<n+1>_{i-j}}{(i-j)!}$.
I try to prove this equation but I am not able to do that because I reached this situation with a product inside a summatory: $\sum_{k=0}^{i-j} \frac{<n>_{k}}{k!} = \sum_{k=0}^{i-j} \frac{<n-1>_{k}}{k!} * \frac{n-1+k}{n-1}$.
I hope someone among you can help me in thinking about this demonstration.
Thanks in advance!
(I prefer the notation $x^{\underline k}$ to $\langle x\rangle_k$ for the falling factorial and will use it.) Note that
$$\frac{n^{\underline k}}{k!}=\binom{n}k\;;$$
in fact, the generalized binomial coefficient $\binom{x}k$ is defined by $$\binom{x}k=\frac{x^{\underline k}}{k!}$$ for arbitrary $x$ and non-negative integers $k$. Thus, you’re trying to show that
$$\sum_{k=0}^{i-j}\binom{n-1}k=\binom{n}{i-j}\;.\tag{1}$$
To simplify the notation let $m=i-j$, so that $(1)$ becomes
$$\sum_{k=0}^m\binom{n-1}k=\binom{n}m\;.$$
Unfortunately, this isn’t true in general. Suppose that $m=2$; then the lefthand side is
$$\binom{n-1}0+\binom{n-1}1=1+n-1=n\;,$$
while the righthand side is
$$\binom{n}2=\frac12n(n-1)\;,$$
and the two are equal only for $n=3$. Let’s start over from the beginning.
For $i\ge j$ let $a_n(i,j)$ be the number of addends needed to compute the $\langle i,j\rangle$ element in a product of $n$ lower triangular matrices; then
$$a_{n+1}(i,j)=\sum_{k=j}^ia_n(i,k)\;.$$
Clearly $a_1(i,j)=1$, so $a_2(i,j)=i-j+1$, and
$$a_3(i,j)=\sum_{k=j}^i(i-k+1)=\sum_{k=1}^{i-j+1}k=\binom{i-j+2}2\;.$$
Take it a step further:
$$a_4(i,j)=\sum_{k=j}^i\binom{i-k+2}2=\sum_{k=2}^{i-j+2}\binom{k}2=\binom{i-j+3}3\;,$$
where the last step is an application of the so-called hockey stick identity; you can find it and several proofs of here and at the question of which that was a duplicate. Note that we also have
$$a_1(i,j)=1=\binom{i-j+0}0$$
and
$$a_2(i,j)=i-j+1=\binom{i-j+1}1\;.$$
All of this not only suggests that in general
$$a_n(i,j)=\binom{i-j+n-1}{n-1}\;,$$
but also suggests how to prove it by induction on $n$ using the hockey stick identity.