Problem

Source: ELMO Shortlist 2023 N4

Tags: Elmo, number theory



Let \(d(n)\) denote the number of positive divisors of \(n\). The sequence \(a_0\), \(a_1\), \(a_2\), \(\ldots\) is defined as follows: \(a_0=1\), and for all integers \(n\ge1\), \[a_n=d(a_{n-1})+d(d(a_{n-2}))+\cdots+ {\underbrace{d(d(\ldots d(a_0)\ldots))}_{n\text{ times}}}.\]Show that for all integers \(n\ge1\), we have \(a_n\le3n\). Proposed by Karthik Vedula