Let n be a positive integer. Find the number of positive integers whose base n representation has some other properties (USAMO 1990)

Question

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

Answer 1

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?