Problem
ALG-B1-M05-P017 Integrality Through an Invariant
#17
★★★★★ Level 5 of 5
The sequence is defined by \(a_1=1\), \(a_{n+1}=a_n^2+a_n\). Prove that \(a_n\) is divisible by \(a_1a_2\cdots a_{n-1}\) for \(n\ge2\).
Notice that \(a_{n+1}=a_n(a_n+1)\).
We prove the stronger statement that \(a_n\) is divisible by the product of all previous terms. The base is clear.
If \(a_n\) is divisible by \(a_1\cdots a_{n-1}\), then \(a_{n+1}=a_n(a_n+1)\) is divisible by \(a_1\cdots a_{n-1}\cdot a_n\). Hence the claim follows by induction.
Strong but accessible induction.