Maths Olympiad Prep

Library / /21 of 97

Combinatorics Difficulty 7.5 National olympiad, round 2 Find the answer

Given a positive integer n n, for all positive integers a1,a2,,an a_1, a_2, \cdots, a_n that satisfy a1\equal1 a_1 \equal{} 1, ai\plus1ai\plus1 a_{i \plus{} 1} \leq a_i \plus{} 1, find i\equal1na1a2ai \displaystyle \sum_{i \equal{} 1}^{n} a_1a_2 \cdots a_i.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given a positive integer n n , for all positive integers a1,a2,,an a_1, a_2, \cdots, a_n that satisfy a1=1 a_1 = 1 and ai+1ai+1 a_{i+1} \leq a_i + 1 , we aim to find the sum i=1na1a2ai \displaystyle \sum_{i=1}^{n} a_1 a_2 \cdots a_i .

To solve this problem, we denote f(m,n) f(m, n) as the sum a1a2an \sum a_1 a_2 \cdots a_n where a1=m a_1 = m and ai+1ai+1 a_{i+1} \leq a_i + 1 .

We observe that if a1=m a_1 = m , then a2 a_2 can take values from 1 1 to m+1 m+1 . Therefore, we have:
f(m,n+1)=ma2a3an+1=m(f(1,n)+f(2,n)++f(m+1,n)). f(m, n+1) = m \cdot \sum a_2 a_3 \cdots a_{n+1} = m \left( f(1, n) + f(2, n) + \cdots + f(m+1, n) \right).

We proceed by induction to find a general formula for f(m,n) f(m, n) :
f(m,n)=(2n1m+2n2)(2n1)!!. f(m, n) = \binom{2n-1}{m+2n-2} \cdot (2n-1)!!.

Base Case:
When n=1 n = 1 , it is clear that f(m,1)=m f(m, 1) = m , which satisfies the formula.

Inductive Step:
Assume the formula holds for n n . Then for n+1 n+1 :
f(m,n+1)=m(f(1,n)+f(2,n)++f(m+1,n))=m(2n1)!!((2n12n1)+(2n12n)++(2n1m+2n1)). \begin{align*} f(m, n+1) &= m \left( f(1, n) + f(2, n) + \cdots + f(m+1, n) \right) \\ &= m \cdot (2n-1)!! \left( \binom{2n-1}{2n-1} + \binom{2n-1}{2n} + \cdots + \binom{2n-1}{m+2n-1} \right). \end{align*}

Using the Hockey Stick Identity:
(2n12n1)+(2n12n)++(2n1m+2n1)=(2nm+2n). \binom{2n-1}{2n-1} + \binom{2n-1}{2n} + \cdots + \binom{2n-1}{m+2n-1} = \binom{2n}{m+2n}.

Thus:
f(m,n+1)=m(2n1)!!(2nm+2n)=m(2n1)!!(m+2n)!m!(2n)!=(2n+1)!!2n+12n+m. \begin{align*} 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}. \end{align*}

This confirms that the formula holds for n+1 n+1 .

Therefore, for m=1 m = 1 , we have:
f(1,n)=(2n1)!!. f(1, n) = (2n-1)!!.

Hence, the desired sum is:
i=1na1a2ai=(2n1)!!. \sum_{i=1}^{n} a_1 a_2 \cdots a_i = (2n-1)!!.

The answer is: \boxed{(2n-1)!!}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.