## Problem 4

How many positive integers can be written in base $\mathrm{n}$ so that (1) the integer has no two digits the same, and (2) each digit after the first differs by one from an earlier digit? For example, in base 3 , the possible numbers are $1,2,10,12,21,102,120,210$.


## Solution

Answer: $2^{n+1}-2 n-2$.

We use a more elaborate induction hypothesis. We claim that for base $n+1$, the following numbers of integers satisfy the two conditions: $2^{n+1}-2 n-2$ not using the digit $n ; 2^{n}-1$ with the digit $n$ is the last position; $2^{\mathrm{n}-1}$ with the digit $\mathrm{n}$ in the last but 1 position; $2^{\mathrm{n}-2}$ with the digit $\mathrm{n}$ having 2 following digits; $2^{\mathrm{n}-3}$ with the digit $\mathrm{n}$ having 3 following digits; $\ldots ; 1$ with the digit $\mathrm{n}$ having $\mathrm{n}$ following digits.

Thus for $\mathrm{n}=2$, the claim is that there are 2 numbers only involving 0 and $1(1,10), 3$ numbers with 2 as the last digit $(2,12,102), 2$ numbers with one digit after $2(21,120)$ and 1 number with two digits after $2(210)$. Suppose this holds for base $n+1$.

If we add up the various possibilities we get $2^{n+1}-2 n-2+\left(2^{n}-1+2^{n-1}+2^{n-2}+\ldots+1\right)=2^{n+1}-2 n-2+2^{n+1}-$ $2=2^{n+2}-2(n+1)-2$. The number of base $n+2$ integers not involving the digit $n+1$ is the same as the number of base $n+1$ numbers, which is (by induction and the addition above) $2^{n+2}-2(n+1)-2$. If a base $n+2$ number has the digit $\mathrm{n}+1$ in the last place, then either that is the only digit in the number or the earlier digits must form a base $n+1$ number with the digit $n$ in it. There are $\left(2^{n}-1+2^{n-1}+\ldots+1\right)=2^{n+1}-2$ such numbers, so in total we have $2^{n+1}-1$ base $n+2$ numbers with $n+1$ in the last place. If a base $n+2$ number has the digit $n+1$ in the penultimate place, then either the number has $n+1$ as the first digit, in which case it must be $n+1 n$, or the other digits form a base $\mathrm{n}+1$ number with the digit $\mathrm{n}$ in the penultimate place or earlier. There are $2^{\mathrm{n}-1}+\ldots+$ $1=2^{\mathrm{n}}-1$ such numbers. So $2^{\mathrm{n}}$ in total. Similarly for the other possibilities.

Finally, we need to check the answer for $n=2\left(1,10\right.$, so two numbers and $\left.2^{2+1}-2 \cdot 2-2=8-4-2=2\right)$.

