Let $P_{b}(n)$ be the $n$th palindromic number in base $b$. I read on Wikipedia that the sum $$\sum_{n=1}^\infty \frac{1}{P_{10}(n)}$$ converges, but I have no idea how to prove it.
I tried using combinatorics to count the "density" of the palindromes and establish an upper bound that was easy to prove was convergent, but my counting just got too complicated. How do I prove that this converges? Furthermore, how can I prove (or disprove) that it converges for any $b\ge 2, b\in \mathbb N$?
On
The number of $d$-digit base $b$ palindromes is $(b-1)b^{\lceil{\frac d2}\rceil-1}$. (The first digit can’t be zero, the rest of the first “half” of the digits can be anything; the rest of the digits have only one possible value.) Each $d$-digit palindrome is at least as big as the number $100\dots001=b^{d-1}+1$. Thus the sum you seek is bounded above by $\displaystyle\sum_{d=1}^\infty \frac{(b-1)b^{\lceil{\frac d2}\rceil-1}}{b^{d-1}+1}$. Roughly (you can fill in the details), this is $\displaystyle\sum_{d=1}^\infty \frac{b^{{\frac d2}}}{b^d}$, a convergent geometric series with ratio $\displaystyle\frac1{\sqrt b}$.
For numbers with $k$ digits there are $10^{k/2}$ palindromes if $k$ is even and $10^{(k+1)/2}$ if $k$ is odd. The reciprocal of such a palindrome is less than $10^{-(k-1)}$. The sum of all the reciprocal palindromes of $k$ digits is less than $10^{-k/2}$. The sum over $k$ is a geometric series with ratio less than $1$, so the sum converges. The same argument works in any base.