Putnam-Style Sequences Problem

Question

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$.

Answer 1

(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:

1. $a_1^{(p)}=p$
2. $a_{p-1}^{(p)}=p$
3. $a_j^{(p)}\leq a_{j+1}^{(p)}$ for all positive integers $j$
4. $a_p^{(p)}>p$

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

Answer 2

First, $S_n$ is weakly increasing.

Second, term $1$ and $p-1$ of $S_{p}$ are $p$.