Back to problem set

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 x1=1x_1 = 1, x2=3x_2 = 3, and xn+1=1n+1∑i=1nxi  for n=2,3,…\displaystyle{ x_{n+1} = \frac{1}{n + 1} \sum_{i = 1}^n x_i \ \textrm{ for} \ n = 2, 3, … }

Find lim⁡n→∞xn\displaystyle{ \lim_{n \to \infty} x_n } and give a proof of your answer.

Hints

Hint #1

Calculate the first few values xix_i for i=3,4,5,…i = 3, 4, 5, … and see if you notice a pattern. See the section “Numerical exploration” below for what this looks like.

Hint #2

Expand the algebraic expression for xnx_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.

Answer

This has just the answer, not the full proof. Try solving it first!

lim⁡n→∞xn=43 \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:

x1=1x2=3x3=13(1+3)=43x4=14(1+3+43)=14⋅163=43x5=15(1+3+43+43)=15⋅203=43x6=16(1+3+43+43+43)=16⋅243=43 \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 11 at every step, and by adding the most recent prior value 43\frac{4}{3}, we keep coming up with the same outcome! Why is that?

Also, if we’re doing manual addition (instead of adding 43\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 xix_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:

x1=1x2=3x3=13(1+3)=13⋅4=43x4=14(4+43)=14⋅163=43x5=15(163+43)=15⋅203=43x6=16(203+43)=... \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 {x6\lbrace x_6, x7x_7, ..., x10}x_{10} \rbrace x6=16(203+43)=16⋅243=43x7=17(243+43)=17⋅283=43x8=18(283+43)=18⋅323=43x9=19(323+43)=19⋅363=43x10=110(363+43)=110⋅403=43 \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 x3x_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 xnx_n depends on prior values xn−1,xn−2,…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:

xn+2=1n+2∑i=1n+1xi=1n+2(xn+1+∑i=1nxi)xn+1=1n+1∑i=1nxi=1n+1(xn+∑i=1n−1xi)xn=1n∑i=1n−1xi=... \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 xix_i.

Thus, let’s expand the main formula algebraically:

xn+1=1n+1∑i=1nxifor  n=3,4,... (given)=1n+1(xn+∑i=1n−1xi)split xn from the sum=1n+1(1n∑in−1xi+∑i=1n−1xi)expand xn=1n+1(n+1n∑i=1n−1xi)combine and simplify=1n∑i=1n−1xicancel (n+1) factor=xnfor  n=3,4,... \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:

xn+1=xnfor n=3,4,… x_{n+1} = x_n \qquad \textrm{for} \ n = 3, 4, …

which also means that:

xn=43for n=3,4,… x_n = \frac{4}{3} \qquad \textrm{for} \ n = 3, 4, …

and hence,

lim⁡n→∞xn=43■ \lim_{n \to \infty} x_n = \boxed{ \frac{4}{3} } \qquad \blacksquare