Kvant Math Problem 1523

Let

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 29m20s
Source on kvant.digital

Problem

Consider the sequence $a_1=1$, $a_2=2$, $a_3=3$, $a_4=4$, $a_5=5$, $a_6=119$, $a_{n+1}=a_1a_2\ldots a_n-1$ under $n\ge 5$. Prove that $$a_1^2+a_2^2+\ldots+a_{70}^2=a_1a_2\ldots a_{70}.$$

L. D. Kurlandchik

Solution

Let

$$P_n=a_1a_2\cdots a_n,\qquad S_n=a_1^2+a_2^2+\cdots+a_n^2.$$

Since

$$a_1=1,\ a_2=2,\ a_3=3,\ a_4=4,\ a_5=5,\ a_6=119,$$

we have

$$P_5=1\cdot2\cdot3\cdot4\cdot5=120,$$

hence

$$a_6=P_5-1.$$

For every $n\ge5$ the recurrence gives

$$a_{n+1}=P_n-1,$$

and therefore

$$P_{n+1}=P_n(P_n-1).$$

The key point is to find a quantity that remains invariant.

Define

$$D_n=S_n-P_n.$$

For $n\ge5$,

$$\begin{aligned} D_{n+1} &=S_{n+1}-P_{n+1}\ &=(S_n+a_{n+1}^2)-P_n(P_n-1). \end{aligned}$$

Using $a_{n+1}=P_n-1$,

$$\begin{aligned} D_{n+1} &=S_n+(P_n-1)^2-\bigl(P_n^2-P_n\bigr)\ &=S_n-P_n+1\ &=D_n+1. \end{aligned}$$

Thus, for every $n\ge5$,

$$D_{n+1}=D_n+1.$$

It remains to compute $D_6$.

First,

$$S_6=1^2+2^2+3^2+4^2+5^2+119^2 =55+14161 =14216.$$

Also,

$$P_6=1\cdot2\cdot3\cdot4\cdot5\cdot119 =120\cdot119 =14280.$$

Hence

$$D_6=S_6-P_6=14216-14280=-64.$$

Since $D_{n+1}=D_n+1$, induction yields

$$D_n=D_6+(n-6)=n-70.$$

Indeed, $D_6=-64=6-70$, and each step increases both sides by $1$.

Taking $n=70$ gives

$$D_{70}=70-70=0.$$

Therefore

$$S_{70}=P_{70},$$

that is,

$$a_1^2+a_2^2+\cdots+a_{70}^2 = a_1a_2\cdots a_{70}.$$

This is exactly the required identity. ∎