Disclaimer: these are my personal solutions; they have not been reviewed, so be careful relying on them as there might be errors. Some competitions may have official solutions from the contest publishers which you may wish to refer to instead if you’re looking for verified solutions.
Problem 1
Let $x_1 = 1$, $x_2 = 3$, and $\displaystyle{ x_{n+1} = \frac{1}{n + 1} \sum_{i = 1}^n x_i \ \textrm{ for} \ n = 2, 3, … }$
Find $\displaystyle{ \lim_{n \to \infty} x_n }$ and give a proof of your answer.
Hints
Calculate the first few values $x_i$ for $i = 3, 4, 5, …$ and see if you
notice a pattern. See the section “Numerical exploration” below for what this
looks like.Hint #1
Expand the algebraic expression for $x_n$ and see what you can do to simplify
it. Consider how you might want to compute values in hint #1 above more
efficiently to help you visualize it. The “Solution” section has the details.Hint #2
Answer
This has just the answer, not the full proof. Try solving it first!
$$ \lim_{n \to \infty} x_n = \boxed{ \frac{4}{3} } $$
Numerical exploration
Try solving the problem first before peeking at the solution!
Let’s expand a few of the initial values to see if there’s a pattern and build some intuition:
$$ \begin{align*} x_1 & = 1 \\ x_2 & = 3 \\ x_3 & = \frac{1}{3} \left( 1 + 3 \right) = \frac{4}{3} \\ x_4 & = \frac{1}{4} \left( 1 + 3 + \frac{4}{3} \right) = \frac{1}{4} \cdot \frac{16}{3} = \frac{4}{3} \\ x_5 & = \frac{1}{5} \left( 1 + 3 + \frac{4}{3} + \frac{4}{3} \right) = \frac{1}{5} \cdot \frac{20}{3} = \frac{4}{3} \\ x_6 & = \frac{1}{6} \left( 1 + 3 + \frac{4}{3} + \frac{4}{3} + \frac{4}{3} \right) = \frac{1}{6} \cdot \frac{24}{3} = \frac{4}{3} \\ \end{align*} $$First, it’s interesting that the function appears to have become a constant! We keep incrementing the denominator by $1$ at every step, and by adding the most recent prior value $\frac{4}{3}$, we keep coming up with the same outcome! Why is that?
Also, if we’re doing manual addition (instead of adding $\frac{4}{3}$ at every step, as that’s the only change), we are doing a lot of duplicated work: we keep computing the whole sum of prior values of $x_i$ every time, can we reuse some of the work to simplify it for ourselves?
Note that there’s quite a bit of repetition between consecutive terms:
$$ \newcommand\redbx[1]{\fcolorbox{red}{none}{$ \displaystyle{ #1 } $}} \newcommand\grnbx[1]{\fcolorbox{green}{none}{$ \displaystyle{ #1 } $}} \newcommand\blubx[1]{\fcolorbox{blue}{none}{$ \displaystyle{ #1 } $}} \newcommand\purbx[1]{\fcolorbox{purple}{none}{$ \displaystyle{ #1 } $}} % \begin{align*} % \redbx{abc} \cdot \blubx{abc} \times \grnbx{\frac{def}{ghi}} \\ % \end{align*} \begin{align*} x_1 & = 1 \\ x_2 & = 3 \\ x_3 & = \frac{1}{3} \left( 1 + 3 \right) = \frac{1}{3} \cdot \redbx{4} = \blubx{\frac{4}{3}} \\ x_4 & = \frac{1}{4} \left( \redbx{4} + \blubx{\frac{4}{3}} \right) = \frac{1}{4} \cdot \grnbx{\frac{16}{3}} = \purbx{\frac{4}{3}}\\ x_5 & = \frac{1}{5} \left( \grnbx{\frac{16}{3}} + \purbx{\frac{4}{3}} \right) = \frac{1}{5} \cdot \redbx{\frac{20}{3}} = \blubx{\frac{4}{3}} \\ x_6 & = \frac{1}{6} \left( \redbx{\frac{20}{3}} + \blubx{\frac{4}{3}} \right) = ... \\ \end{align*} $$Expand to see further calculation of $\lbrace x_6$, $x_7$, ..., $x_{10} \rbrace$
$$ \begin{align*} x_6 & = \frac{1}{6} \left( \frac{20}{3} + \frac{4}{3} \right) = \frac{1}{6} \cdot \frac{24}{3} = \frac{4}{3} \\ x_7 & = \frac{1}{7} \left( \frac{24}{3} + \frac{4}{3} \right) = \frac{1}{7} \cdot \frac{28}{3} = \frac{4}{3} \\ x_8 & = \frac{1}{8} \left( \frac{28}{3} + \frac{4}{3} \right) = \frac{1}{8} \cdot \frac{32}{3} = \frac{4}{3} \\ x_9 & = \frac{1}{9} \left( \frac{32}{3} + \frac{4}{3} \right) = \frac{1}{9} \cdot \frac{36}{3} = \frac{4}{3} \\ x_{10} & = \frac{1}{10} \left( \frac{36}{3} + \frac{4}{3} \right) = \frac{1}{10} \cdot \frac{40}{3} = \frac{4}{3} \\ \end{align*} $$So, it looks like it becomes a constant after $x_3$, why is that? Can you reuse the pattern that keeps repeating somehow? Try solving the problem now yourself, before looking at the solution below.
Solution
Try solving the problem first before peeking at the solution!
Since each $x_n$ depends on prior values $x_{n-1}, x_{n-2}, …$, we note that there are overlaps between consecutive values in terms of what they’re including in their sums, so they should have common terms we can evaluate and combine.
Namely:
$$ \newcommand\redbx[1]{\fcolorbox{red}{none}{$ \displaystyle{ #1 } $}} \newcommand\grnbx[1]{\fcolorbox{green}{none}{$ \displaystyle{ #1 } $}} \newcommand\blubx[1]{\fcolorbox{blue}{none}{$ \displaystyle{ #1 } $}} \newcommand\purbx[1]{\fcolorbox{purple}{none}{$ \displaystyle{ #1 } $}} \begin{align*} x_{n+2} & = \frac{1}{n+2} \sum_{i=1}^{n+1} x_i = \frac{1}{n+2} \left( x_{n+1} + \redbx{ \sum_{i=1}^n x_i } \right) \\ x_{n+1} & = \frac{1}{n+1} \redbx{ \sum_{i=1}^n x_i } = \frac{1}{n+1} \left( x_n + \blubx{ \sum_{i=1}^{n-1} x_i } \right) \\ x_{n } & = \frac{1}{n } \blubx{ \sum_{i=1}^{n-1} x_i } = ... \\ \end{align*} $$Note that the pairs of matching colored boxes are the same terms, which appear as common subterms for different values of $x_i$.
Thus, let’s expand the main formula algebraically:
$$ \begin{align*} x_{n+1} & = \frac{1}{n + 1} \sum_{i = 1}^n x_i & \qquad \textrm{for \ $n = 3, 4, ...$ (given)} \\ & = \frac{1}{n + 1} \left( x_n + \sum_{i = 1}^{n - 1} x_i \right) & \qquad \textrm{split $x_n$ from the sum} \\ & = \frac{1}{n + 1} \left( \frac{1}{n} \sum_i^{n-1} x_i + \sum_{i = 1}^{n - 1} x_i \right) & \qquad \textrm{expand $x_n$} \\ & = \frac{1}{n + 1} \left( \frac{n + 1}{n} \sum_{i = 1}^{n - 1} x_i \right) & \qquad \textrm{combine and simplify} \\ & = \frac{1}{n} \sum_{i = 1}^{n - 1} x_i & \qquad \textrm{cancel $(n+1)$ factor} \\ & = x_n & \qquad \textrm{for \ $n = 3, 4, ...$} \\ \end{align*} $$Thus, we see that:
$$ x_{n+1} = x_n \qquad \textrm{for} \ n = 3, 4, … $$
which also means that:
$$ x_n = \frac{4}{3} \qquad \textrm{for} \ n = 3, 4, … $$
and hence,
$$ \lim_{n \to \infty} x_n = \boxed{ \frac{4}{3} } \qquad \blacksquare $$