Combinatorics – Number of $n$-Digit Palindromes

Question

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

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. 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.

How do I proceed?

Answer 1

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}$.