![](https://cdn.mathpix.com/cropped/2024_05_06_0ffd3d08f157224b5b77g-28.jpg?height=118&width=2044&top_left_y=1619&top_left_x=10)
[ Sums of numerical sequences and series of differences ]

Auto: Obviousl...

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

a) Find formulas for $T_{2}(n)$ and $T_{3}(n)$.

b) Prove that $T_{k}(n)$ is a polynomial in $n$ of degree $2k$.

c) Indicate a method for finding the polynomials $T_{k}(n)$ for $k=2,3,4, \ldots$ and apply it to find the polynomials $T_{4}(n)$ and $T_{5}(n)$.
a) $2 T_{2}(n)=(1+\ldots+n)^{2}-\left(1^{2}+\ldots+n^{2}\right)=$

$$
\begin{aligned}
& =\left(\frac{n(n+1)}{2}\right)^{2}-\frac{n(n+1)(2 n+1)}{6}=\frac{n(n+1)(n(n+1)-(2 n+1))}{12} \\
& =\frac{n(n+1)\left(3 n^{2}-n-2\right)}{12}=\frac{n(n+1)(n-1)(3 n+2)}{12}
\end{aligned}
$$

$T_{3}(n)$ is found similarly from the equality

$$
6 T_{3}(n)=(1+\ldots+n)^{3}-3\left(1^{2}+\ldots+n^{2}\right)(1+\ldots+n)+2\left(1^{3}+\ldots+n^{3}\right)=
$$

$$
\begin{aligned}
& =n^{2}(n+1)^{2}\left(\frac{n(n+1)}{8}-\frac{2 n+1}{4}+\frac{1}{2}\right)=\frac{n^{2}(n+1)^{2}\left(3 n^{2}-n-2\right)}{8} \\
= & \frac{(n+1)^{2} n^{2}(n-1)(n-2)}{8}
\end{aligned}
$$

(For formulas for the sums of squares and cubes, see problems $\underline{60282}, \underline{61431}$.

b) Let's divide all the terms of the sum $T_{k}(n)$ into two groups: in one, include those products that contain $n$, and in the other - the rest. From this,

$$
T_{k}(n)-T_{k}(n-1)=n T_{k-1}(n-1) \quad(*)
$$

Now the statement is proved by induction.

Base case. $T_{1}(n)=1+\ldots+n=\frac{n(n+1)}{2}$.

Inductive step. By the inductive hypothesis, $n T_{k-1}(n-1)$ is a polynomial of degree $2 k-1$ in $n$. Now, from problem 61434, it follows that there exists a polynomial of degree $2 k$ whose values coincide with $T_{k}(n)$ for all natural $n$.

c) The recurrence formula (*) and the obvious equality $T_{k}(k)=k$! allow us to sequentially compute the polynomials $T_{k}(n)$: the formula (*) can be considered as a system of equations for the coefficients of the polynomial $T^{2}$.

To reduce the number of unknowns, note that the values of the polynomial $T_{k}$ make sense not only for natural $n \geq k$, but for all integers (and even real) $n$. Looking at the formulas for $T_{1}, T_{2}, T_{3}$, it is reasonable to assume that

$$
T_{k}(k-1)=T_{k}(k-2)=\ldots=T_{k}(1)=T_{k}(0)=T_{k}(-1)=0
$$

This assumption does not contradict the recurrence formula.

For example, we will seek $T_{4}(n)$ in the form $(n+1) n(n-1)(n-2)(n-3) P(n)$, where $P(n)=a n^{3}+b n^{2}+c n+d$. Writing (*) for $k=4$ and canceling by $n(n-1)(n-2)(n-3)$, we get

$$
(n+1) P(n)-(n-4) P(n-1)=\frac{n^{2}(n-1)}{48}
$$

or $48(n+1)\left(a n^{3}+b n^{2}+c n+d\right)-48(n-4)\left(a(n-1)^{3}+b(n-1)^{2}+c(n-1)+d\right)=n^{2}(n-1)$.

We can then equate the coefficients of like powers (for example, comparing the coefficients of $n^{3}$, we get

$48(a+b+4 a+3 a-b)=1$, from which $a=1 / 384)$.

Or we can substitute "small" values of $n$. For example, for $n=1$ we get the relation $2 a+2 b+2 c+5 d=0$. Continuing in this way, we will find the expression for $T_{4}$ given in the answer. Similarly, $T_{5}$ is found.

## Answer

a) $T_{2}(n)=\frac{n\left(n^{2}-1\right)(3 n+2)}{24}, T_{3}(n)=\frac{(n+1)^{2} n^{2}(n-1)(n-2)}{48}$;

c) $T_{4}(n)=\frac{n\left(n^{2}-1\right)(n-2)(n-3)\left(15 n^{3}+15 n^{2}-10 n-8\right)}{5760}$,

$$
\begin{gathered}
T_{5}(n)=\frac{(n+1)^{2} n^{2}(n-1)(n-2)(n-3)(n-4)\left(3 n^{2}-n-6\right)}{11520} . \\
\underline{\text { Send a comment }}
\end{gathered}
$$

## Problem