Palindromic Numbers

Date: 01/04/98 at 15:42:04
From: Zeyneb Akyildiz
Subject: Palindromic numbers

Dear Dr.Math,

My friends and I are working on an extra credit assignment. We were 
wondering how many palindromic numbers exist that are less than      
100 000. 

Could you also help us with the formula?

Thank you,
Zeyneb Akyildiz and friends

Date: 01/04/98 at 16:18:37
From: Doctor Pete
Subject: Re: Palindromic numbers

Hi,

One way to do this is to simply count palindromes with a fixed number 
of digits, and take the sum of these values from 1 digit to 5 (why 
not 6?). 

For instance, how many palindromes are there with 4 digits?  Well, a 
4-digit palindrome must be of the form

     abba,

where a is between 1 and 9, and b is between 0 and 9 (again, why?).  
How many ways can you choose values of a, and choose values of b?  
Well, since a and b do not need to be distinct, there are 9 ways to 
choose a and 10 ways to choose b, hence 90 ways to choose pairs (a,b) 
to give a palindromic number. So there are 90 4-digit palindromes.

Similarly, examine the number of 1-, 2-, 3-, and 5-digit palindromes, 
and then take the sum.

If you want a formula, notice that the number of 3-digit palindromes 
is equal to the number of 4-digit palindromes, because a 3-digit 
palindrome is of the form

     aba,

and with the same restrictions on a and b as we saw before, this 
also gives rise to 9(10) = 90 possibilities. Now, show that if n 
is odd, the number of n-digit palindromes is equal to the number of 
(n+1)-digit palindromes.  

Finally, consider an n-digit palindrome (again n is odd), so it has 
the representation

     [a1][a2][a3]...[an]...[a3][a2][a1]

(here I have written the digits as a1, a2, a3, ..., an, so the above 
is not a product but the digit representation). Notice that for the 
digits a2, a3, ... an, they are all between 0 and 9, and the only 
digit that cannot be 0 is a1. So how many ways can you choose n-tuples 
(a1,a2,a3,...,an)?  Put all of this together and you get a formula.

-Doctor Pete,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/