Problem

Source: RMO 2024 Q6

Tags: number theory



Let $n \geq 2$ be a positive integer. Call a sequence $a_1, a_2, \cdots , a_k$ of integers an $n$-chain if $1 = a_2 < a_ 2 < \cdots < a_k =n$, $a_i$ divides $a_{i+1}$ for all $i$, $1 \leq i \leq k-1$. Let $f(n)$ be the number of $n$-chains where $n \geq 2$. For example, $f(4) = 2$ corresponds to the $4$-chains $\{1,4\}$ and $\{1,2,4\}$. Prove that $f(2^m \cdot 3) = 2^{m-1} (m+2)$ for every positive integer $m$.