Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.