Let a 'good number' denote a non-negative integer with no digit of $p-1$ when expressed in base $p$. Note that we have a 1-1 correspondence between the integers and the good numbers, i.e. we can express each integer in base $p-1$ and read it in base $p$, producing a good number, and conversely we can read each good number's digits in base $p$ as if they were in base $p-1$ to produce an integer. Thus, it suffices to simply show that $a_{n}$ is the $n$th (counting from $n=0$) good number. Note that for $a_{0}$ through $a_{p-2}$, $a_{n}$ is automatically the $n$th good number. We shall now proceed by induction, i.e. we shall show that if $a_{0}$ through $a_{k}$ are the first $k+1$ good numbers, then $a_{k+1}$ is the next good number. So assume that $a_{0}$ through $a_{k}$ are the first $k+1$ good numbers for some $k \ge p-2$. We now prove the following lemma: Lemma 1 Any arithmetic sequence of length $p$ contains a number with a digit of $p-1$ in base $p$ Proof: Consider an arithmetic sequence with first term $x$ and common difference $d$ given by \[x+ad \] for integer $0\le a \le p-1$. Let $d_{m}$ denote the rightmost nonzero digit of $d$, and say that this is in the $m$th place (i.e. the coefficient of $d^{m}$). Also, let $x_{m}$ denote the $m$th digit of $x$. Now, when we form the arithmetic sequence, the $m$th digit will be formed by successively adding $d_{m}$ to $x_{m}$ and taking that value $\mod{p}$, as a digit must be between $0$ and $p-1$ and any excess multiples of $p$ carry over to higher digit places. We also note that because all the digits to the right of $d_{m}$ (if any) are zero, none of them will carry over to the $m$th place. Because $p$ is prime, $d_{m}$ is nonzero by definition, and $a$ ranges over all the residues $\mod{p}$, the digit in this place must sometime be $\equiv p-1 \mod{p}$ and thus $= p-1$, and in particular this occurs when $a \equiv d_{m}^{-1}(-x_{m}-1) \mod{p}$ (which exists because $d_{m}$ is nonzero and thus has an inverse in this prime modulus). Therefore, a number with a digit of $p-1$ must appear somewhere in a sequence of length $p$, and the lemma is proven. This now means that the next good number does not form any arithmetic sequences of length $p$ with $a_{0}$ through $a_{k}$ because none of them have digits of $p-1$. If we can show that each of the integers between $a_{k}$ and the next good number do form arithmetic sequences of length $p$ with (some of) the numbers $a_{0}$ through $a_{k}$, then the next good number is the lowest number that does not and we are done. Consider an integer, call it $s$, that is between $a_{k}$ and the next good number. By definition of the 'next' good number, it is not good and has a digit of $p-1$ somewhere. Now form a sequence by replacing each $p-1$ digit of $s$ with each of the integers $0$ through $p-2$ successively, i.e. replace each $p-1$ digit with 0 and this is the first number in the sequence, replace them all with 1 and this is the second number in the sequence, etc., and finally place $s$ at the end of the sequence. This forms an arithmetic sequence of length $p$ whose common difference is a number with a digit of 1 at each place where $s$ had a digit of $p-1$ in base $p$. Because all the terms before $s$ in this sequence have no digits of $p-1$ and are thus good numbers and we assumed that $a_{0}$ through $a_{k}$ consisted of all the good numbers less than $s$, all of the members of this sequence besides $s$ are members of $\{a_{0},a_{1},...,a_{k}\}$, meaning that $s$ does form an arithmetic sequence of length $p$ with (some of) $a_{0}$ through $a_{k}$. Therefore, the next good number is the lowest number that does not and therefore equals $a_{k+1}$, completing the induction, so $a_{n}$ is always the $n$th good number or the number formed by reading $n$ in base $p-1$ and reading the result in base $p$. QED

Consider $a_{p-1}$. The preceding $p-1$ terms clearly form the arithmetic sequence $\{0,1,\ldots,p-2\}$, hence we cannot have $a_{p-1}=p-1$, meaning $a_{p-1}=p$. After this, we can have $a_{p}=p+1$, $a_{p+1}=p+2$, etc., until we have another $p-1$ terms that form an arithmetic sequence, in which we will need $a_{2(p-1)}=2p$, instead of $2p-1$, as it would complete an arithmetic sequence of length $p$. Then, we can verify by induction that $a_{k(p-1)}=kp$, and also $a_{k(p-1)+c}=kp+c$, where $c<p-1$. Using $a_{k(p-1)+c}=kp+c$, we find that $n$, when represented in base $p-1$, consists of the digits of the number $k$ in base $p-1$, followed by the single digit $c$, as $c<p-1$. Finally, $kp+c$ in base $p$ looks the same, beginning with the digits of $k$, followed by the digit $c$, as $c<p-1<p$. Therefore, we conclude that $a_{n}$ is the number obtained by writing $n$ in base $p-1$ and reading in base $p$. $\Box$

Define a "set number" as a number that can be written in base $p$ without the digit $p-1$. Starting with zero, these are $g_0, g_1, \cdots$. Define a “non-set number” as all other nonnegative integers. We must prove that $a_i=g_i$ for all nonnegative $i$. We do this by induction: Base case: $a_0, a_1, \cdots, a_{p-2}$ are all set numbers because $a_k=k$ for $0 \leq k \leq p-2$. Assume that $a_0, a_1, \cdots, a_k$ are the first $k+1$ set numbers. Thus, $a_i=g_i$ for $0 \leq i \leq k$. Lemma 1: $g_{k+1}$ can be added onto $a_0, a_1, \cdots, a_k$ without creating arithmetic sequences of length $p$ with $a_0, a_1, \cdots, a_k$. Proof: we prove this by showing that all arithmetic sequences of length $p$ have at least one non-set number. All terms of the sequence are of the form $y+md$, for $0 \leq m \leq p-1$. Let $y=Q(p)=c_np^n+\cdots+c_0p^0$ such that $0 \leq c_i \leq p-1$ for $0 \leq i \leq n$. Each term of the sequence has a unique representation as this type of polynomial, because each coefficient represents a digit base $p$. Similarly, let $d=H(p)= z_np^n+\cdots+z_0p^0$ such that $0 \leq z_i \leq p-1$ for $0 \leq i \leq n$. Choose distinct $m$ and $j$ between $0$ and $p-1$. So $y+md=Q(p)+mH(p)$ and $y+jd=Q(p)+jH(p)$. Choose $r$ between $0$ and $n$. We will show that for no value of $r$ are the coefficients of $p^r$ in $Q(p)+mH(p)$ and $Q(p)+jH(p)$ congruent modulo $p$ (for $m \neq j$). Since there are $p$ possible values of $m$ and $j$ and $p$ possible values modulo $p$, there must be at least one coefficient of $p^r$ that is $p-1$ modulo $p$ for some term in the sequence. If this is true, then that term will be $k_np^n+\cdots+k_{r+1}p^{r+1}+k_rp^r+\cdots+k_0p^0$. $k_r=pl+(p-1)$, so the term is $k_np^n+\cdots+(k_{r+1}+l)p^{r+1}+(p-1)p^r+\cdots+k_0p^0$, which is a non-set number. The coefficient of $p^r$ in $Q(p)+mH(p)$ is $c_r+mz_r$, and $c_r+jz_r$ in $Q(p)+jH(p)$. Assume $c_r+mz_r \equiv c_r+jz_r$ (mod $p$). Then $m \equiv j$ (mod $p$) since $p$ and $z_r$ are relatively prime. But $m$ and $j$ are between $0$ and $p-1$ and $m \neq j$, so they are distinct modulo $p$. Contradiction. This completes the lemma. Lemma 2: $g_{k+1}$ is the smallest term that can be added to $a_0, a_1, \cdots, a_k$ without creating arithmetic sequences of length $p$ with $a_0, a_1, \cdots, a_k$. Proof: we prove this by showing that all numbers between $a_k=g_k$ and $g_{k+1}$ form arithmetic sequences of length $p$ with $a_0, a_1, \cdots, a_k$. Let $b=b_np^n+\cdots+b_0p^0$ such that $g_k<b<g_{k+1}$. This means that $b$ is a non-set number. Let $B(p)=(p-1)(p^{e_r}+\cdots+p^{e_0})$ and let $G(p)=z_{f_s}p^{f_s}+\cdots+z_{f_0}p^{f_0}$ such that $0 \leq z_{f_i} \leq p-2$ for $0 \leq i \leq s$, $\{f_0, f_1, \cdots, f_s\} \cap \{e_0, e_1, \cdots, e_r\} = \{{\o}\}$, $\{f_0, f_1, \cdots, f_s\} \cup \{e_0, e_1, \cdots, e_r\} = \{0,1,\cdots,n\}$, and $b=B(p)+G(p)$. Since $b$ is a non-set number, $B(p) \neq 0$. Let $d= p^{e_r}+\cdots+p^{e_0}$. We see that $b$ is the $p-1$th term of an arithmetic sequence of length $p$, first term $G(p)$, common difference $d=\frac{B(p)}{p-1}$. All the other terms in this sequence are $G(p)+m\frac{B(p)}{p-1}$ for $0 \leq m \leq p-1$. Since $G(p)$ has no coefficients equal to $p-1$, $G(p)+m\frac{B(p)}{p-1}$ has no coefficients equal to $p-1$ for $0 \leq m \leq p-2$. Thus, all other terms in the sequence are set numbers less than $b$, so they are contained within $a_0, a_1, \cdots, a_k$. This completes the lemma. Thus, the smallest term that can be added to $a_0, a_1, \cdots, a_k$ that will not create any arithmetic sequences of length $p$ with any of the preceding terms is $g_{k+1}$. Thus, $a_j=g_j$ for all nonnegative $j$, by strong induction. $Q.E.D.$