RU-ALLRUSSIAN 1972 Problem 5

A sequence of finite sets of positive integers is defined as follows. $\mathrm{S_0 = \{m\}}$ , where $\mathrm{m > 1}$ . Then given $\mathrm{S_n}$ you derive $\mathrm{S_{n + 1}}$ by taking $\mathrm{k^2}$ and $\mathrm{k + 1}$ for each element k of $\mathrm{S_n}$ . For example, if $\mathrm{S_0 = \{5\}}$ , then $\mathrm{S_2 = \{7, 26, 36, 625\}}$ . Show that $\mathrm{S_n}$ always has $2^{\mathrm{n}}$ distinct elements.