Combinatorial Summation

Question

I'm trying to solve the following question:
If $s_n$ is the sum of first $n$ natural numbers, then prove that $$2(s_1s_{2n}+s_2s_{2n-1}+\dots+s_ns_{n+1})=\frac{(2n+4)!}{5!(2n-1)!}$$ This is where I've come so far:

The general term of $(1-x)^{-2n}$ happens to be $t_{r+1}=\frac{(2n+r-1)!}{(2n-1)!r!}x^r$ and therefore the 6th term, i.e, $t_{5+1}=t_6=\frac{(2n+4)!}{(2n-1)!5!}x^5$, which looks like the RHS of the question I'm trying to solve.

Second, I found that $$(1-x)^{-3}=s_1+s_2x+\dots+s_nx^{n-1}+\dots$$ It's clear that the LHS must be something like, $(1-x)^{-a}(1-x)^{-b}$. But I'm not able to find one such combination which would give me $2(s_1s_{2n}+s_2s_{2n-1}+\dots+s_ns_{n+1})$.

Help is greatly appreciated.

Answer 1

More generally, $$\sum_{k=3}^{m-2}\binom{k-1}{2}\binom{m-k}{2}=\binom{m}{5},$$ which you can prove combinatorially by counting $5$-subsets of $\{1,\dots,m\}$. The RHS is clear. For the LHS, condition on the third largest (median) element $k$ chosen. Then $\binom{k-1}{2}$ counts the selections of $2$ elements that are less than $k$, and $\binom{m-k}{2}$ counts the selections of $2$ elements that are greater than $k$.

For the OP's identity, rewrite $$2\sum_{k=1}^{n} s_k s_{2n+1-k} =\sum_{k=1}^{2n} s_k s_{2n+1-k} =\sum_{k=1}^{2n} \binom{k+1}{2} \binom{2n+2-k}{2} =\sum_{k=3}^{2n+2} \binom{k-1}{2} \binom{2n+4-k}{2} $$ and take $m=2n+4$.

Answer 2

If you'd be open to another strategy, we want to prove$$\sum_{k=1}^ns_ks_{2n+1-k}=\frac{n(n+1)(n+2)(2n+1)(2n+3)}{30}.$$This is an exercise in arithmetic once you notice$$s_k=\tfrac12k(k+1)\implies s_ks_{2n+1-k}=\tfrac14k(k+1)(2n+1-k)(2n+2-k)$$is a quartic in $k$, and use the Faulhaber's formulae$$\begin{align}\sum_{k=1}^nk&=\tfrac12n(n+1),\\\sum_{k=1}^nk^2&=\tfrac16n(n+1)(2n+1),\\\sum_{k=1}^nk^3&=\tfrac14n^2(n+1)^2,\\\sum_{k=1}^nk^4&=\tfrac{1}{30}n(6n^4+15n^3+10n^2-1).\end{align}$$

Answer 3

Here is a rather detailed algebraic derivation. We recall that multiplication of a generating function $A(x)$ with $\frac{1}{1-x}$ gives the sum of the coefficients of $A(x)$: \begin{align*} A(x)=\sum_{n=0}^\infty \color{blue}{a_n}x^n\qquad\qquad \frac{1}{1-x}A(x)=\sum_{n=0}^\infty\left(\color{blue}{\sum_{k=0}^na_k}\right)x^n \end{align*}

We so derive \begin{align*} \frac{1}{1-x}&=\sum_{n=0}^\infty x^n\\ \frac{1}{(1-x)^2}&=\sum_{n=0}^\infty \left(\sum_{k=0}^n 1\right)x^n=\sum_{n=0}^\infty(n+1)x^n\\ \frac{1}{(1-x)^3}&=\sum_{n=0}^\infty \sum_{k=0}^n\left(k+1\right)x^n \\ &=\sum_{n=0}^\infty s_{n+1}x^n=1+3x+6x^2+\cdots\tag{1} \end{align*}

Squaring $\frac{1}{(1-x)^3}$ we get from (1) thanks to the Cauchy product \begin{align*} \frac{1}{(1-x)^6}=\sum_{m=0}^\infty \left(\sum_{k=0}^m s_{k+1}s_{m-k+1}\right)x^m\tag{2} \end{align*}

Now we are ready to show the validity of \begin{align*} 2\left(s_1s_{2n}+s_2s_{2n-1}+\ldots+s_ns_{n+1}\right)=\frac{(2n+4)!}{5!(2n-1)!}\qquad\qquad n\geq 1\tag{3} \end{align*}

We obtain for $n\geq 1$: \begin{align*} \color{blue}{2\left(s_1s_{2n}+s_2s_{2n-1}+\cdots+s_ns_{n+1}\right)} &=2\sum_{k=0}^{n-1}s_{k+1}s_{2n-k}\\ &=\sum_{k=0}^{n-1}s_{k+1}s_{2n-k}+\sum_{k=0}^{n-1}s_{n-k}s_{n+1+k}\tag{4}\\ &=\sum_{k=0}^{n-1}s_{k+1}s_{2n-k}+\sum_{k=n}^{2n-1}s_{2n-k}s_{k+1}\tag{5}\\ &=\sum_{k=0}^{2n-1}s_{k+1}s_{2n-k}\tag{6}\\ &=[x^{2n-1}]\frac{1}{(1-x)^6}\tag{7}\\ &=[x^{2n-1}]\sum_{j=0}^\infty\binom{-6}{j}(-x)^j\tag{8}\\ &=[x^{2n-1}]\sum_{j=0}^\infty\binom{j+5}{j}x^j\tag{9}\\ &=\binom{2n+4}{2n-1}=\binom{2n+4}{5}\tag{10}\\ &\,\,\color{blue}{=\frac{(2n+4)!}{5!(2n-1)!}} \end{align*} and the claim (3) follows.

Comment:

• In (4) we write the right-hand sum by changing the order of summation: $k\to n-1-k$.

• In (5) we shift the index of the right-hand sum by $n$.

• In (7) we use that (6) is the coefficient of $x^{2n-1}$ in (2).

• In (8) we make a binomial series expansion.

• In (9) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}$.

• In (10) we select the coefficient of $x^{2n-1}$ and use $\binom{p}{q}=\binom{p}{p-q}$.