0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

(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.

$\endgroup$
  • $\begingroup$ thank you very much, you really help me! Just one thing: I suppose that :$\frac{n^{\underline k}}{k!}=\binom{n+k-1}k\$. Am I wrong? Thanks again! $\endgroup$ – delca85 Jul 3 '16 at 19:09
  • $\begingroup$ @Bianca: You’re welcome. No, $$\frac{n^{\underline k}}{k!}=\frac{n(n-1)(n-2)\ldots(n-k+1)}{k!}=\frac{n!}{k!(n-k)!}=\binom{n}k\;.$$ $\endgroup$ – Brian M. Scott Jul 3 '16 at 19:11
  • $\begingroup$ :) sorry, maybe I haven't been clear: the Pochammer symbol I am using is the one related to the rising factorial: $<n>_k = n (n+1) ... (n + k - 1)$. Sorry for the mistake! $\endgroup$ – delca85 Jul 3 '16 at 19:55
  • $\begingroup$ @Bianca: Ah, okay; I’d write that $n^{\overline k}$. Yes, $n^{\overline k}=\binom{n+k-1}k$. $\endgroup$ – Brian M. Scott Jul 3 '16 at 19:58
  • $\begingroup$ Perfect! I really appreciate your help! $\endgroup$ – delca85 Jul 4 '16 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.