Задача
ALG-B1-M05-P017 Целочисленность через инвариант
#17
★★★★★ Уровень 5 из 5
Последовательность задана \(a_1=1\), \(a_{n+1}=a_n^2+a_n\). Докажите, что \(a_n\) делится на \(a_1a_2\cdots a_{n-1}\) при \(n\ge2\).
Заметьте, что \(a_{n+1}=a_n(a_n+1)\).
Докажем сильнее: \(a_n\) делится на произведение всех предыдущих членов. База очевидна.
Если \(a_n\) делится на \(a_1\cdots a_{n-1}\), то \(a_{n+1}=a_n(a_n+1)\) делится на \(a_1\cdots a_{n-1}\cdot a_n\). Значит, утверждение верно по индукции.
Сильная, но доступная индукция.