How many positive integers can be written in base 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: 2n+1 - 2n - 2.
We use a more elaborate induction hypothesis. We claim that for base n+1, the following numbers of integers satisfy the two conditions: 2n+1- 2n - 2 not using the digit n; 2n - 1 with the digit n is the last position; 2n-1 with the digit n in the last but 1 position; 2n-2 with the digit n having 2 following digits; 2n-3 with the digit n having 3 following digits; ... ; 1 with the digit n having n following digits.
Thus for 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 2n+1 - 2n - 2 + (2n - 1 + 2n-1 + 2n-2 + ... + 1) = 2n+1 - 2n - 2 + 2n+1 - 2 = 2n+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) 2n+2 - 2(n+1) - 2. If a base n+2 number has the digit 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 (2n - 1 + 2n-1 + ... + 1) = 2n+1 - 2 such numbers, so in total we have 2n+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 n+1 number with the digit n in the penultimate place or earlier. There are 2n-1 + ... + 1 = 2n - 1 such numbers. So 2n in total. Similarly for the other possibilities.
Finally, we need to check the answer for n = 2 (1, 10, so two numbers and 22+1 - 2·2 - 2 = 8 - 4 - 2 = 2).
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002