# How many $n$-digit palindromes are there?

How can one count the number of all $n$-digit palindromes? Is there any recurrence for that?

Thanks.

I'm not sure if my reasoning is right, but I thought that for n=1 we have 10 such numbers (including 0), for n=2 we obviously have 9 possibilities, for n=3 we can choose 'extreme digits' in 9 ways and then there are 10 possibilities for digits in the middle. For n=4 again we choose extreme digits in 9 ways and middle digits in 10 ways, and so on. It seems that for even lengths of numbers we have $9 \cdot 10^{\frac{n}{2}-1}$ palindromes and for odd lengths $9 \cdot 10^{n-2}$;. But this is certainly not even close to a proper solution of this problem.

-
Hint: How many $7$-digit or $8$-digit palindromes start with $1000$? How many start with $1001$? – Erick Wong Jan 26 '13 at 20:52

Details depend on whether for example $0110$ counts as a $4$-digit palindrome. We will suppose it doesn't. This makes things a little harder.

If $n$ is even, say $n=2m$, the first digit can be any of $9$, then the next $m-1$ can be any of $10$, and then the rest are determined. So there are $9\cdot 10^{m-1}$ palindromes with $2m$ digits.

If $n$ is odd, say $n=2m+1$, then the same sort of reasoning yields the answer $9\cdot 10^{m}$.

-
Thanks. I see I was wrong about odd ns. – Hagrid Jan 26 '13 at 21:05
@Hagrid: In the odd case, the "middle" person can be anything. – André Nicolas Jan 26 '13 at 22:07

An n-digit number abc...xyz can be mapped to the 2n-digit palindrome abc...xyzzyx...bca, and to the (2n-1)-digit palindrome abc...xyzyx...bca. So the number of 2n-digit palindromes and (2n-1)-digit palindromes is simply the number of n-digit numbers: $9 \times 10^{n-1}$.

-