Putnam-Style Sequences Problem Let $S_1$ denote the sequence of positive integers $1,2,3,4,5,6,\ldots,$ and define the sequence $S_{n+1}$ in terms of $S_n$ by adding $1$ to those integers in $S_n$ which are divisible by $n$.  Thus, for example, $S_2$ is $2,3,4,5,6,7, \ldots,$ and $S_3$ is $3,3,5,5,7,7,\ldots$.  Prove that an arbitrary prime number, $p$, satisfies the property that the first $p - 1$ integers in $S_p$ are $p$.
 A: First, $S_n$ is weakly increasing.
Second, term  $1$ and $p-1$ of $S_{p}$ are $p$.
A: (This is perhaps a little bit messy. Hope you can follow...)
Let's call the sequence
$$
S_n=\left\{a_j^{(n)}\right\}_{j=1}^\infty
$$
where the superscript refers to the step in the $S_n$ sequence. It is clear that
$$
a_j^{(n)}\leq a_{j+1}^{(n)}.
$$
So, what is $a_1^{(p)}$? Let's use some induction.

Base case: $ a_1^{(1)}=1 $
Inductive step: If $a_1^{(n)}=n$, then this should imply that $a_1^{(n+1)}=n+1$.
If $a_1^{(n)}=n$, then $n$ divides $a_1^{(n)}$ and $a_1^{(n+1)}=a_1^{(n)}+1=n+1$.

So we can conclude that $a_1^{(p)}=p$.
We also need to check $a_{p-1}^{(p)}$. But, $p$ is a prime and $a_{p-1}^{(1)}=p-1$ (from the initial sequence). Since 1 divides $p-1$ we get $a_{p-1}^{(2)}=p$. So since it is a prime, $a_{p-1}^{(k)}=p$ for all $k\leq p$.
Also, since 1 divides $a_p^{(1)}=p$, $a_p^{(n)}>p$ for $n>1$. 
Thus, to conclude. Since:


*

*$a_1^{(p)}=p$

*$a_{p-1}^{(p)}=p$

*$a_j^{(p)}\leq a_{j+1}^{(p)}$ for all positive integers $j$

*$a_p^{(p)}>p$


it follows that the $p-1$ first terms are equal to $p$. 
