Let n be a positive integer. Find the number of positive integers whose base n representation has some other properties (USAMO 1990) Let $n$ be a positive integer. Find the number of positive integers whose base $n$ representation consists of distinct digits with the property that except for the leftmost digit, every digit differs by $\pm1$ from some digit further to the left.
Through a lot of guesswork I managed to conclude that if $a_n$ denotes the number of suitable base $n$ representations, then $a_{n+1}=a_n+2^{n+1}-2$ and since $a_1=0$ then $a_{n+1}=2^{n+2}-4-2n$ which equates to $a_n=2^{n+1}-4-2(n-1)=2^{n+1}-2n-2$.
Could you please explain to me how I could have mathematically come up with the recursive relation $a_{n+1}=a_n+2^{n+1}-2$?
 A: Establishing the recurrence for base $n+1$ (which uses the digits from $0$ to $n$).
(Wishful thinking, will revisit if this doesn't work out) $a_n$ corresponds to those strings which do not use $n$.
It remains to count the number of strings have the digit $n$ in them. We do so by creating a (almost) bijection.
Given any string of length $k+1$, we can associate it to a new string of length $k$ of "Up" and "Down" as follows. Starting from the left, ignore the first digit,

*

*If the $i+1$th digit is higher than all of the previous digits, call the new string "Up" in the $i$th position from the left.

*If the $i+1$th digit is lower than all of the previous digits, call the new string "Down" in the $i$th position from the left.

Conversely, given any string of length $k$ of "Up" and "Down", we can associate it to a string of length $k+1$ that contains $n$.

*

*Fill in $n, n-1, \ldots$ in the following order.

*Focus on "Up", work from right to left.

*Fill in the starting digit.

*Focus on "Down", work from left to right.

This is almost a bijection, except in 1 specific instance (Which one? Why is this unique?)
This establishes that there are $1 + 2 + 2^2 + \ldots 2^n -1 = 2^{n+1} - 2$ strings with $n$ in them.
Thus $ a_{n+1} = a_n + 2^{n+1} - 2 $.

As an explicit example of the almost bijection, with $n = 2$,
$\{\} \leftrightarrow 2$
$ \{ \uparrow \}  \leftrightarrow 12$
$ \{ \downarrow \}  \leftrightarrow 21$
$ \{ \uparrow, \uparrow \}  \leftrightarrow 012$
$ \{ \uparrow, \downarrow \}  \leftrightarrow 120$
$ \{ \downarrow, \downarrow \}  \leftrightarrow 210$
$ \{ \downarrow, \uparrow \}  \leftrightarrow 102$
Which number is duplicated?
