# How to prove an inequality for a special structure of strictly triangular matrix

The problem I cause is attached below. I am trying to prove the inequality.

By using small $M$, I found that the terms on the left side of the inequality are part of the terms of the expansion on the right side. But I always feel dizzy when I try to prove the inequality by expanding the left side and the right side and then comparing them...

I am thinking that is there any properties for the power of strictly triangular matrix, or the matrix L1 norm can be used to the proof? Thank you in advance.

$$Q_{M}=\left[\begin{array}{ccccc} 0\\ k_{1} & 0\\ \frac{1}{2}k_{2} & \frac{1}{2}k_{1} & 0\\ \vdots & & \ddots & \ddots\\ \frac{1}{M-1}k_{M-1} & \frac{1}{M-1}k_{M-2} & \cdots & \frac{1}{M-1}k_{1} & 0 \end{array}\right]$$

Prove that for $\forall n,M\in\mathbb{N}_{+}$,

$$n!\left\Vert Q_{M}^{n}\right\Vert _{1}\leq\left(k_{1}+\frac{1}{2}k_{2}+\cdots\frac{1}{M-1}k_{M-1}\right)^{n}$$

-
Hi! Could you briefly define $\left\Vert Q_{M}^{n}\right\Vert _{1}$ for me please? – vanguard2k Aug 20 '12 at 14:13
Hi. Thank you~~ Well, actually the L1 norm means: $$\left\Vert A\right\Vert _{1}=\max_{j}\sum_{i=1}^{N}a_{ij}$$ Therefore, the define is: $$\left\Vert Q_{M}^{n}\right\Vert _{1}=\sum_{p=n+1}^{M}\sum_{i_{n-1}=2}^{p-(n-1)}\sum_{i_{n-2}=i_{n-1}+1}^{p-(n-2)‌​}\cdots\sum_{i_{1}=i_{2}+1}^{p-1}$$ $$\times\frac{1}{\left(p-1\right)\left(i_{1}-1\right)\cdots\left(i_{n-1}-1\right)}‌​k_{p-i_{1}}k_{i_{1}-i_{2}}\cdots k_{i_{n-1}-1}$$ – Chang Aug 21 '12 at 1:25
Thank you! Have you tried using the multinomial theorem on the rhs then and tried dropping some terms? One more thing: are the $k_i$ nonnegative? en.wikipedia.org/wiki/Multinomial_theorem – vanguard2k Aug 21 '12 at 7:03
Glad to receive your reply. First, all $k_i$ are positive. Sorry I forgot to mention it. Second, I tried the multinomial theorem on the rhs and it is the only way I know to do...But when considering the multinomial theorem, $$\left(k_{1}+\frac{1}{2}k_{2}+\cdots\frac{1}{M-1}k_{M-1}\right)^{n}=\sum_{j_{1}+ \cdots+j_{n-1}=n}\left(\begin{array}{c} n\\ j_{1},\ldots j_{n-1} \end{array}\right)k_{1}^{j_{1}}\cdots k_{M-1}^{j_{M-1}}$$ I tried but failed to make each term has the same footer format because I hope to find that the lhs is just a part of rhs next. – Chang Aug 21 '12 at 8:53
Sorry i didnt have time to do some calculations recently. I noticed that you made a mistake while applying the multinomial theorem: the coefficients ($\frac{1}{2^{j_2}}\cdots \frac{1}{(M-1)^{j_{M-1}}}$) seem to be missing. – vanguard2k Aug 22 '12 at 6:51