1

For a fixed integers $j$ and $k$ with $1\leq j<k\leq n-1$, I am trying to find the coefficient of $x_{n+j}\cdot x_{n+k}$ in the following product - \begin{equation} { \prod_{l=2}^n\left(1+\sum_{i=1}^{l-1}c_{il}\cdot x_{n+i}\right) =(1+c_{12}\cdot x_{n+1})\ (1+c_{13}\cdot x_{n+1}+c_{23}\cdot x_{n+2})\cdots\\ \qquad\qquad\cdots\left(1+\sum_{i=1}^{l-1}c_{il}\cdot x_{n+i}\right)\cdots\left(1+\sum_{i=1}^{n-1}c_{in}\cdot x_{n+i}\right) \tag{1} } \end{equation}

Here $c_{ij}$ are integers.

I tried it for $n=3,\ 4,\ 5$ and $6$ and observed a pattern in the coefficients and came up with the formula - $$\sum_{l=1}^{n-k}\left[c_{k,k+l}\left(\sum_{\substack{i=j+1\\ i\neq k+l}}^n c_{j,i}\right)\right] \tag{2} $$

Now I would like to prove it rigorously by induction(??) on $n$. Unfortunately, I have no idea how to proceed with the induction step.

I assume that for the product (1), the coefficient of $x_{n+j}\cdot x_{n+k}$ is (2).

Now I need to to find the coeffecient of $x_{n+1+j}\cdot x_{n+1+k}$ in the product $$\prod_{l=2}^{n+1}\left(1+\sum_{i=1}^{l-1}c_{il}\cdot x_{n+1+i}\right)$$ This is what confuses me. I can't simply write the new product in terms of the old one. So how would I proceed?

Thank you.

R_D
  • 7,312

1 Answers1

1

I try a solution, somewhat complicated.

1) Let $Q_n(x)$ your expression, here $x=(x_{n+1},...x_{2n-1})$. We have $Q_n(x)=\sum a_k x_{n+1}^{k_1}...x_{2n-1}^{k_{n-1}}$. Note that the $k_l$ are $\leq n-1$; for the case of $n+1$, we have the variables $x_{n+2},...x_{2n+1}$, and the power of the variables in $Q_{n+1}$ are $\leq n$

2) Now let $m$ an integer $m\geq n+1$(large with respect to $n+1$). Then we replace in $Q_n$ (and also in $Q_{n+1}$) the $x_{n+i}$ by $t^{m^{i-1}}$, where $t$ is a new variable. We note $P_n(t)$ the polynomial in one variable $t$ obtained in this way from $Q_n(x)$. The unicity of the decompostion of the integers in base $m$ show that the different monomials in $Q_n$ gives only one term in $P_n(t)$. We have then that the coefficient $A_{n,j,k}$ of $x_{n+j}x_{n+k}$ in $Q_n$ is the coefficient of $t^{m^{j-1}+m^{k-1}}$ in $P_n(t)$, and the coefficient $A_{n+1,j,k}$ of $x_{n+1+j}x_{n+1+k}$ in $Q_{n+1}$ is the coefficient of $t^{m^{j}+m^{k}}$ in $P_{n+1}(t)$.

3) Now it is easy to show that $$P_{n+1}(t)=P_n(t^m)(1+\sum_{l=1}^n c_{l,n+1}t^{m^l})$$

4) We get that $$A_{n+1,j,k}=A_{n,j,k}+\sum_{l=1}^{n}c_{l,n+1}{\rm Coef}(t^{m^{j-1}+m^{k-1}-m^{l-1}}, P_n(t))$$

5) Now, if $l\not =j$ or $k$, the coefficient of $t^{m^{j-1}+m^{k-1}-m^{l-1}}$ in $P_n(t)$ is zero, as there is no term of the form $x_{n+j}x_{n+k}x_{n+l}^{-1}$ in $Q_n(x)$(or by the unicity of the decomposition in base $m$). Hence

$$A_{n+1,j,k}=A_{n,j,k}+c_{k,n+1}{\rm Coef}(t^{m^{j-1}}, P_n(t))+c_{j,n+1}{\rm Coef}(t^{m^{k-1}}, P_n(t))$$

And now, from the expression of $P_n(t)$, we see that we obtain the coefficient of $t^{m^{j-1}}$ by choosing the coefficient of $t^{m^{j-1}}$ in one of the factors, (if it exist) and then choosing the constant term $1$ in all other factors; same remark for the coefficient of $t^{m^{k-1}}$. Hence

$$A_{n+1,j,k}=A_{n,j,k}+c_{k,n+1}(\sum_{i=j+1}^{n}c_{j,i})+c_{j,n+1}(\sum_{i=k+1}^{n}c_{k,i})$$

6) It remain to show that the expression you have guessed gives the same result as above; if I am not wrong, this is the case.

Kelenner
  • 18,734
  • 26
  • 36