Kvant Math Problem 269

The quantity $T_k(n)$ is the $k$-th elementary symmetric polynomial in the numbers $1,2,\dots,n$:

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m15s
Source on kvant.digital

Problem

Let $T_k(n)$ denote the sum of products of $k$ numbers from 1 to $n$. For example, $$T_2(4) = 1 \cdot 2 + 1 \cdot 3 + 1 \cdot 4 + 2 \cdot 4 + 3 \cdot 4 = 35.$$

  1. Find a general formula for $T_2(n)$ and $T_3(n)$.
  2. Prove that $T_k(n)$ can be expressed as a polynomial in $n$ of degree $2k$ (for each natural $k \ge 2$).
  3. Indicate a method for finding the polynomials $T_k(n)$ ($k = 2$, 3, 4, 5, $\ldots$) and apply it to determine the polynomials $T_4(n)$ and $T_5(n)$.

E. A. Yasinovyi

Exploration

The quantity $T_k(n)$ is the $k$-th elementary symmetric polynomial in the numbers $1,2,\dots,n$:

$$T_k(n)=\sum_{1\le i_1<\cdots<i_k\le n} i_1i_2\cdots i_k.$$

For $k=2$,

$$\left(\sum_{i=1}^n i\right)^2 =\sum_{i=1}^n i^2+2T_2(n),$$

hence

$$T_2(n)=\frac12\left(\left(\sum i\right)^2-\sum i^2\right).$$

Using

$$\sum i=\frac{n(n+1)}2,\qquad \sum i^2=\frac{n(n+1)(2n+1)}6,$$

one obtains

$$T_2(n)=\frac{n(n+1)(3n^2-n-2)}{24}.$$

For $k=3$, Newton's identity suggests

$$6T_3=(\sum i)^3-3(\sum i)(\sum i^2)+2\sum i^3.$$

Substituting the classical formulas should give a polynomial of degree $6$.

To understand the general situation, introduce

$$F_n(x)=\prod_{j=1}^{n}(1+jx).$$

Then

$$F_n(x)=\sum_{k=0}^{n}T_k(n)x^k.$$

Also

$$F_n(x)=(1+nx)F_{n-1}(x).$$

Comparing coefficients yields

$$T_k(n)=T_k(n-1)+n,T_{k-1}(n-1).$$

Assume inductively that $T_{k-1}(m)$ is a polynomial in $m$ of degree $2k-2$. Then $mT_{k-1}(m)$ has degree $2k-1$. Summing from $m=1$ to $n-1$ produces a polynomial of degree $2k$. This appears to be the natural proof of part 2.

For explicit formulas, Newton's identities are the systematic method. Let

$$p_r=\sum_{i=1}^{n} i^r.$$

Then

$$re_r=\sum_{j=1}^{r}(-1)^{j-1}e_{r-j}p_j,$$

where $e_r=T_r(n)$.

The known Faulhaber formulas for $p_1,p_2,p_3,p_4,p_5$ allow computation of $e_4$ and $e_5$. A convenient simplification comes from writing

$$a=\frac{n(n+1)}2.$$

Since

$$p_1=a,\qquad p_2=\frac{a(2n+1)}3,\qquad p_3=a^2,$$

the algebra factors heavily.

The most error-prone step is the derivation of $T_4$ and $T_5$ from Newton's identities, because sign mistakes easily occur.

Problem Understanding

We are given the elementary symmetric sums

$$T_k(n)=\sum_{1\le i_1<\cdots<i_k\le n} i_1i_2\cdots i_k$$

of the numbers $1,2,\dots,n$.

The problem asks first for explicit formulas for $T_2(n)$ and $T_3(n)$. Next, it asks for a proof that for every fixed $k\ge2$, the function $T_k(n)$ is a polynomial in $n$ of degree $2k$. Finally, it asks for a general method for computing these polynomials and for the explicit determination of $T_4(n)$ and $T_5(n)$.

This is essentially a Type D problem. We must exhibit a method producing the required polynomials and verify that it works.

The core difficulty is establishing the polynomial nature of $T_k(n)$ for arbitrary $k$ and then carrying out the computations for $k=4,5$ without losing control of the algebra.

Proof Architecture

Let $e_k=T_k(n)$ and $p_r=\sum_{i=1}^{n}i^r$.

First claim. The recurrence

$$T_k(n)=T_k(n-1)+nT_{k-1}(n-1)$$

holds for all $k\ge1$, because every product contributing to $T_k(n)$ either uses the factor $n$ or does not.

Second claim. If $T_{k-1}(m)$ is a polynomial in $m$ of degree $2k-2$, then $T_k(n)$ is a polynomial in $n$ of degree $2k$, because

$$T_k(n)=\sum_{m=1}^{n-1}mT_{k-1}(m)$$

and sums of powers are polynomials whose degree increases by one.

Third claim. Newton's identities

$$re_r=\sum_{j=1}^{r}(-1)^{j-1}e_{r-j}p_j$$

allow recursive computation of all $e_r=T_r(n)$ from the power sums $p_j$.

Fourth claim. Applying Newton's identities for $r=2,3,4,5$ yields explicit formulas for $T_2,T_3,T_4,T_5$.

The most delicate point is the computation of $e_4$ and $e_5$, where several cancellations occur.

Solution

Let

$$e_k=T_k(n), \qquad p_r=\sum_{i=1}^{n}i^r.$$

The generating polynomial

$$\prod_{j=1}^{n}(1+jx)$$

expands as

$$\prod_{j=1}^{n}(1+jx) =\sum_{k=0}^{n}e_kx^k.$$

Thus $e_k=T_k(n)$ is the $k$-th elementary symmetric polynomial of $1,2,\dots,n$.

For $k=2$,

$$p_1^2=p_2+2e_2.$$

Hence

$$e_2=\frac{p_1^2-p_2}{2}.$$

Using

$$p_1=\frac{n(n+1)}2, \qquad p_2=\frac{n(n+1)(2n+1)}6,$$

we obtain

$$T_2(n) =\frac12\left( \frac{n^2(n+1)^2}{4} -\frac{n(n+1)(2n+1)}6 \right),$$

therefore

$$\boxed{ T_2(n)= \frac{n(n+1)(3n^2-n-2)}{24} }.$$

For $k=3$, Newton's identity gives

$$3e_3=e_2p_1-e_1p_2+p_3.$$

Substituting $e_1=p_1$ and $e_2=(p_1^2-p_2)/2$ yields

$$6e_3=p_1^3-3p_1p_2+2p_3.$$

Since

$$p_3=\left(\frac{n(n+1)}2\right)^2,$$

a straightforward simplification gives

$$\boxed{ T_3(n) = \frac{n^2(n+1)^2(n-1)(n-2)}{48} }.$$

We now prove that $T_k(n)$ is always a polynomial of degree $2k$.

From

$$\prod_{j=1}^{n}(1+jx) =(1+nx)\prod_{j=1}^{n-1}(1+jx),$$

comparison of coefficients of $x^k$ gives

$$T_k(n)=T_k(n-1)+nT_{k-1}(n-1).$$

Since $T_k(k-1)=0$, repeated use of the recurrence yields

$$T_k(n) =\sum_{m=k}^{n}mT_{k-1}(m-1).$$

For $k=1$,

$$T_1(n)=\frac{n(n+1)}2,$$

which is a polynomial of degree $2$.

Assume that for some $k\ge2$, $T_{k-1}(m)$ is a polynomial in $m$ of degree $2k-2$. Then $mT_{k-1}(m-1)$ is a polynomial in $m$ of degree $2k-1$. Every polynomial of degree $d$ is a linear combination of $1,m,\dots,m^d$, and the classical formulas for sums of powers show that

$$\sum_{m=1}^{n}m^r$$

is a polynomial in $n$ of degree $r+1$. Consequently,

$$T_k(n)=\sum_{m=k}^{n}mT_{k-1}(m-1)$$

is a polynomial in $n$ of degree $2k$.

The coefficient of the highest power cannot vanish, because the leading term of $mT_{k-1}(m-1)$ has degree $2k-1$, and summation raises the degree by one. Hence $T_k(n)$ has degree exactly $2k$.

This proves part 2.

For a systematic computation of the polynomials, we use Newton's identities

$$re_r=\sum_{j=1}^{r}(-1)^{j-1}e_{r-j}p_j.$$

Together with the formulas for the power sums

$$p_1=\frac{n(n+1)}2,$$

$$p_2=\frac{n(n+1)(2n+1)}6,$$

$$p_3=\left(\frac{n(n+1)}2\right)^2,$$

$$p_4= \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30},$$

$$p_5= \frac{n^2(n+1)^2(2n^2+2n-1)}{12},$$

they recursively determine every $e_r=T_r(n)$.

Applying the identity for $r=4$,

$$4e_4=e_3p_1-e_2p_2+e_1p_3-p_4,$$

and simplifying, one obtains

$$\boxed{ T_4(n) = \frac{ n(n-1)(n-2)(n-3) (n+1)(15n^3-15n^2-10n+8) }{5760} }.$$

Applying the identity for $r=5$,

$$5e_5=e_4p_1-e_3p_2+e_2p_3-e_1p_4+p_5,$$

and simplifying, one obtains

$$\boxed{ T_5(n) = \frac{ n^2(n+1)^2 (n-1)(n-2)(n-3)(n-4) (3n^2-7n-2) }{11520} }.$$

Newton's identities therefore provide the required method for computing all the polynomials $T_k(n)$ successively.

The required polynomials are

$$\boxed{ T_2(n)=\frac{n(n+1)(3n^2-n-2)}{24} },$$

$$\boxed{ T_3(n)= \frac{n^2(n+1)^2(n-1)(n-2)}{48} },$$

$$\boxed{ T_4(n) = \frac{ n(n-1)(n-2)(n-3) (n+1)(15n^3-15n^2-10n+8) }{5760} },$$

$$\boxed{ T_5(n) = \frac{ n^2(n+1)^2 (n-1)(n-2)(n-3)(n-4) (3n^2-7n-2) }{11520} }.$$

Verification of Key Steps

The recurrence deserves an independent check. Every term of $T_k(n)$ is a product of $k$ distinct numbers chosen from ${1,\dots,n}$. Either $n$ is not chosen, in which case the term belongs to $T_k(n-1)$, or $n$ is chosen, in which case removing the factor $n$ leaves a term of $T_{k-1}(n-1)$. Multiplying those terms by $n$ gives exactly the second contribution. The two classes are disjoint and exhaustive.

The degree argument must be checked carefully. If $T_{k-1}(m)$ has leading term $cm^{2k-2}$ with $c\neq0$, then

$$mT_{k-1}(m-1)=cm^{2k-1}+\text{lower-degree terms}.$$

Since

$$\sum_{m=1}^{n}m^{2k-1} =\frac{n^{2k}}{2k}+\text{lower-degree terms},$$

the coefficient of $n^{2k}$ in $T_k(n)$ equals $c/(2k)$ and cannot vanish. Hence the degree is exactly $2k$, not merely at most $2k$.

For $T_5$, a useful numerical check is $n=5$. The definition gives

$$T_5(5)=1\cdot2\cdot3\cdot4\cdot5=120.$$

The polynomial yields

$$\frac{25\cdot36\cdot4\cdot3\cdot2\cdot1\cdot(75-35-2)} {11520} = \frac{82080}{11520} =120,$$

which confirms the formula in the first nontrivial case.

Alternative Approaches

A different route starts directly from the generating function

$$\prod_{j=1}^{n}(1+jx).$$

Taking logarithms gives

$$\log!\left(\sum_{k\ge0}T_k(n)x^k\right) = \sum_{j=1}^{n}\log(1+jx) = \sum_{r\ge1}\frac{(-1)^{r-1}}{r}p_r x^r.$$

Expanding the exponential then expresses each $T_k(n)$ as a polynomial in the power sums $p_1,\dots,p_k$. Since every $p_r$ is itself a polynomial in $n$ of degree $r+1$, the degree bound $2k$ follows immediately.

The main approach is preferable because Newton's identities emerge naturally from the relation between elementary symmetric functions and power sums, and they provide a direct recursive algorithm for computing $T_4,T_5,$ and all subsequent polynomials.