Kvant Math Problem 40
For the first sum,
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m30s
Source on kvant.digital
Problem
Find the sum $$1\cdot n + 2\cdot (n-1) + 3\cdot (n-2)+ \ldots + n\cdot 1.$$
Try to solve the following, more general problem: find the sum $$\begin{aligned} S_{n,k}={}&[1\cdot 2\cdot \ldots \cdot k] \times [n(n-1)\cdot\ldots\cdot (n-k+1)]+{}\ {}+{}& [2\cdot 3\cdot \ldots \cdot (k+1)] \times [(n-1)(n-2)\cdot\ldots\cdot (n-k)]+{}\ {}+{}& [3\cdot 4\cdot \ldots \cdot (k+2)] \times [(n-2)(n-1)\cdot\ldots\cdot (n-k-1)]+{}\ {}+{}& {\ldots},{\ldots},{\ldots},{\ldots},{\ldots},{\ldots},{\ldots},{\ldots} +{}\ {}+{}& [(n-k)(n-k+1)\cdot \ldots \cdot (n-1)] \times [(k+1)k \cdot\ldots\cdot 2]+{}\ {}+{}& [(n-k+1)(n-k+2)\cdot \ldots \cdot n] \times [k(k-1) \cdot\ldots\cdot 1]. \end{aligned}$$
V. N. Berezin
Exploration
For the first sum,
$$1\cdot n+2\cdot(n-1)+\cdots+n\cdot1,$$
the $i$-th term is
$$i(n+1-i).$$
Hence
$$\sum_{i=1}^{n} i(n+1-i) =(n+1)\sum_{i=1}^{n}i-\sum_{i=1}^{n}i^2.$$
This already gives a closed form, but the more general problem suggests that a combinatorial reformulation is preferable.
Let
$$T_r=[r(r+1)\cdots(r+k-1)],[ (n-r+1)(n-r)\cdots(n-r-k+2)].$$
Then $S_{n,k}=\sum_{r=1}^{n-k+1}T_r$.
Writing products through factorials,
$$T_r=\frac{(r+k-1)!}{(r-1)!}\cdot \frac{(n-r+1)!}{(n-r-k+1)!}.$$
Since
$$\frac{(r+k-1)!}{(r-1)!}=k!\binom{r+k-1}{k}, \qquad \frac{(n-r+1)!}{(n-r-k+1)!}=k!\binom{n-r+1}{k},$$
we obtain
$$S_{n,k}=(k!)^2 \sum_{r=1}^{n-k+1} \binom{r+k-1}{k}\binom{n-r+1}{k}.$$
The remaining sum resembles Vandermonde's convolution. Set
$$j=r+k-1.$$
Then $j$ runs from $k$ to $n$, and
$$S_{n,k}=(k!)^2 \sum_{j=k}^{n} \binom{j}{k}\binom{n+k-j}{k}.$$
Testing small cases helps identify the correct closed form.
For $k=1$,
$$\sum_{j=1}^{n}j(n+1-j) =\binom{n+2}{3}.$$
For $n=3$, $k=1$,
$$3+4+3=10=\binom{5}{3}.$$
For $n=4$, $k=2$,
$$(1\cdot2)(4\cdot3)+(2\cdot3)(3\cdot2)+(3\cdot4)(2\cdot1) =24+36+24=84.$$
On the other hand,
$$(2!)^2\binom{7}{5}=4\cdot21=84.$$
This suggests
$$\sum_{j=k}^{n} \binom{j}{k}\binom{n+k-j}{k} = \binom{n+k+1}{2k+1}.$$
The crucial point is proving this convolution correctly. A careless shift of indices can change the upper parameter by $1$, producing an incorrect answer.
Problem Understanding
The problem asks first for the value of
$$1\cdot n+2\cdot(n-1)+\cdots+n\cdot1,$$
and then for a formula for the more general sum $S_{n,k}$.
This is a Type C problem, since a specific value of a sum must be determined.
The core difficulty is evaluating the convolution hidden inside the general expression. After rewriting each product in terms of binomial coefficients, the problem reduces to a Vandermonde-type identity.
The expected answer is
$$S_{n,k}=(k!)^2\binom{n+k+1}{2k+1}.$$
For $k=1$ this becomes
$$\binom{n+2}{3},$$
which is the value of the original sum.
Proof Architecture
First, express each term of $S_{n,k}$ as a product of two factorial ratios, then as a product of two binomial coefficients multiplied by $(k!)^2$.
Second, reindex the sum to obtain
$$\sum_{j=k}^{n}\binom{j}{k}\binom{n+k-j}{k}.$$
Third, prove the identity
$$\sum_{j=k}^{n}\binom{j}{k}\binom{n+k-j}{k} = \binom{n+k+1}{2k+1}$$
by applying Vandermonde's convolution after a change of variables.
Finally, substitute back to obtain $S_{n,k}$ and specialize to $k=1$.
The step most likely to fail under scrutiny is the index transformation leading to the Vandermonde convolution, because an incorrect shift changes the final binomial coefficient.
Solution
Let
$$T_r=[r(r+1)\cdots(r+k-1)] [(n-r+1)(n-r)\cdots(n-r-k+2)].$$
Then
$$S_{n,k}=\sum_{r=1}^{n-k+1}T_r.$$
Using factorials,
$$T_r= \frac{(r+k-1)!}{(r-1)!} \cdot \frac{(n-r+1)!}{(n-r-k+1)!}.$$
Since
$$\frac{(r+k-1)!}{(r-1)!} = k!\binom{r+k-1}{k},$$
and
$$\frac{(n-r+1)!}{(n-r-k+1)!} = k!\binom{n-r+1}{k},$$
we obtain
$$S_{n,k} = (k!)^2 \sum_{r=1}^{n-k+1} \binom{r+k-1}{k} \binom{n-r+1}{k}.$$
Introduce
$$j=r+k-1.$$
Then $j$ runs from $k$ to $n$, and
$$S_{n,k} = (k!)^2 \sum_{j=k}^{n} \binom{j}{k} \binom{n+k-j}{k}.$$
Now put
$$i=j-k.$$
Then $i=0,1,\ldots,n-k$, and
$$S_{n,k} = (k!)^2 \sum_{i=0}^{n-k} \binom{i+k}{k} \binom{n-i}{k}.$$
Using the symmetry $\binom{a}{b}=\binom{a}{a-b}$,
$$\binom{i+k}{k}=\binom{i+k}{i}.$$
Hence
$$S_{n,k} = (k!)^2 \sum_{i=0}^{n-k} \binom{i+k}{i} \binom{n-i}{k}.$$
Vandermonde's convolution states that for nonnegative integers $r,s,m$,
$$\sum_{i=0}^{m} \binom{r+i}{i} \binom{s-i}{m-i} = \binom{r+s+1}{m}.$$
Taking
$$r=k,\qquad s=n,\qquad m=n-k,$$
gives
$$\sum_{i=0}^{n-k} \binom{i+k}{i} \binom{n-i}{n-k-i} = \binom{n+k+1}{n-k}.$$
Since
$$\binom{n-i}{n-k-i} = \binom{n-i}{k},$$
we obtain
$$\sum_{i=0}^{n-k} \binom{i+k}{i} \binom{n-i}{k} = \binom{n+k+1}{n-k}.$$
Therefore
$$S_{n,k} = (k!)^2 \binom{n+k+1}{n-k}.$$
Using
$$\binom{n+k+1}{n-k} = \binom{n+k+1}{2k+1},$$
we arrive at
$$\boxed{S_{n,k}=(k!)^2\binom{n+k+1}{2k+1}}.$$
For the original problem, $k=1$. Hence
$$1\cdot n+2\cdot(n-1)+\cdots+n\cdot1 = \binom{n+2}{3} = \frac{n(n+1)(n+2)}6.$$
Thus
$$\boxed{1\cdot n+2\cdot(n-1)+\cdots+n\cdot1 = \frac{n(n+1)(n+2)}6}.$$
Verification of Key Steps
The first delicate step is the conversion to binomial coefficients. For the first factor,
$$\frac{(r+k-1)!}{(r-1)!} = \frac{(r+k-1)!}{k!(r-1)!},k! = k!\binom{r+k-1}{k}.$$
The same computation applies to the second factor. Missing one factor of $k!$ would change the final answer by a factor of $(k!)^2$.
The second delicate step is the reindexing. Starting from
$$\binom{r+k-1}{k}\binom{n-r+1}{k},$$
the substitution $j=r+k-1$ gives
$$\binom{j}{k}\binom{n+k-j}{k}.$$
The quantity $n+k-j$ is obtained from
$$n-r+1=n-(j-k+1)+1=n+k-j.$$
A sign error here would alter the upper parameter in the final binomial coefficient.
The third delicate step is the Vandermonde application. With
$$m=n-k,$$
the right-hand side becomes
$$\binom{k+n+1}{n-k}.$$
Using symmetry,
$$\binom{n+k+1}{n-k} = \binom{n+k+1}{2k+1},$$
because
$$(n+k+1)-(n-k)=2k+1.$$
This confirms the final form.
Alternative Approaches
A purely combinatorial proof can be given for
$$\sum_{j=k}^{n}\binom{j}{k}\binom{n+k-j}{k} = \binom{n+k+1}{2k+1}.$$
Count subsets of size $2k+1$ of the set ${0,1,\ldots,n+k}$. Let $j$ be the $(k+1)$-st smallest selected element. Then $j$ must lie between $k$ and $n$. There are $\binom{j}{k}$ ways to choose the $k$ smaller elements and $\binom{n+k-j}{k}$ ways to choose the $k$ larger elements. Summing over all possible $j$ yields the identity.
This combinatorial argument explains the convolution transparently. The factorial and Vandermonde method is shorter and leads directly from the given products to the closed formula, which makes it the more natural approach for this problem.