Find the number of positive integer palindromes written in base , with no zero digits, and whose digits add up to . For example, has these properties. Recall that a palindrome is a number whose representation reads the same from left to right as from right to left.
Note that the palindrome must have an odd number of digits, as palindromes with an even number of digits will always have an even digit sum. Furthermore, the middle digit of our palindrome must be odd. Suppose the middle digit of the palindrome is for integer . The prefix of the integer before the middle digit is a sequence of positive integers whose digit sum is . The number of sequences of positive integers with sum is , so the final answer is
Here we provide two ways to see that the number of sequences of positive integers with sum is :
Method 1:
Case on how many numbers are in the sequence. If there are numbers in the sequence, then by stars and bars there are sequences. Summing over :
Method 2:
List out 's in a row and consider the gaps in between them. In each gap, we may either place a operator or leave it blank and then join terms connected by a . For example if , some examples include:
We see there is a bijection between the sequences and the number of ways to place symbols, so there are total sequences.
The problems on this page are the property of the MAA's American Mathematics Competitions