Given a positive integer $ n$, for all positive integers $ a_1, a_2, \cdots, a_n$ that satisfy $ a_1 = 1$, $ a_{i + 1} \leq a_i + 1$, find $ \displaystyle \sum_{i = 1}^{n} a_1a_2 \cdots a_i$.
Problem
Source: China TST 2002 Quiz
Tags: algebra unsolved, algebra
darij grinberg
31.01.2009 11:40
Shobber, do you mean this? Given a positive integer $ n$, find the sum $ \sum_{\begin{array}{c} a_1,a_2,\cdots ,a_n\text{ positive} \\ \text{integers satisfying} \\ a_1 = 1\text{ and} \\ a_{i + 1} \leq a_i + 1\text{ for all }i\end{array}}\sum_{i = 1}^{n} a_1a_2 \cdots a_i$. In this case, the sum equals $ 1$, $ 5$, $ 28$, $ 190$, $ 1594$ for $ n$ being $ 1$, $ 2$, $ 3$, $ 4$, $ 5$, respectively. I can't find this in Sloane's encyclopedia... darij
vinvin94250
02.01.2016 16:37
First we can show by induction that for $i\in\{1,...,n\}$, we have $a_i\le i$. Thus $ \displaystyle \sum_{i = 1}^{n} a_1a_2 \cdots a_i\le 1!+2!+...+n!$, with equality if and only if $a_i=i$.
CQYIMO42
09.06.2017 05:46
As per request, here is a solution to this problem:
Solution:
For $a_1=m, a_{i+1}\le a_i+1$, denote $f(m,n)$ as the sum $\sum a_1a_2\cdots a_n$.
Observe that if $a_1=m$, then $a_2$ can be $1,2,\cdots m+1$.
Therefore $f(m,n+1)=m\cdot\sum a_2a_3\cdots a_{n+1}=m(f(1,n)+f(2,n)+\cdots+f(m+1,n))$.
Now we will proceed by induction:
$$f(m,n)=\binom{2n-1}{m+2n-2}\cdot(2n-1)!! \ (*)$$
Induct for $n$:
When $n=1$, it is obvious that $f(m,1)=m$, which satisfies (1).
$$f(m,n+1)=m(f(1,n)+f(2,n)+\cdots+f(m+1,n))=m\cdot(2n-1)!!\cdot\left(\binom{2n-1}{2n-1}+\binom{2n-1}{2n}+\cdots+\binom{2n-1}{m+2n-1}\right)$$
Notice that $$\binom{2n-1}{2n-1}+\binom{2n-1}{2n}+\binom{2n-1}{2n+1}+\cdots+\binom{2n-1}{m+2n-1}$$$$=\binom{2n}{2n}+\binom{2n-1}{2n}+\binom{2n-1}{2n+1}+\cdots+\binom{2n-1}{m+2n-1}$$$$=\binom{2n}{2n+1}+\binom{2n-1}{2n+1}+\cdots+\binom{2n-1}{m+2n-1}$$$$=\cdots=\binom{2n}{m+2n}$$
$$f(m,n+1)=m\cdot(2n-1)!!\cdot\binom{2n}{m+2n}=m\cdot(2n-1)!!\cdot\frac{(m+2n)!}{m!(2n)!}=(2n+1)!!\cdot\frac{2n+1}{2n+m}$$
so $(*)$ holds true at $n+1$.
Thus $(*)$ always holds true, and $f(1,n)=(2n-1)!!$.
Therefore the desired sum is $(2n-1)!!$.