Number of binary palindromes in a range I want to find the number of binary palindromes from $1$ to $N$. 
$0 \lt N \lt 2^{32}-1$.
I observed a pattern that if we have an odd-length binary palindrome, it can generate only $1$ even-length palindrome by adding a digit. 
If we have an even-length binary palindrome, it can generate $2$ odd-length palindromes by adding another digit.
How do I solve the problem with or without using this observation?
 A: Suppose $m$ is a palindrome. Any positive binary integer has first digit $1$, so $m$ has last digit $1$, and if $m$ has $k$ digits and $k > 1$, this leaves $k - 2$ digits. If $k$ is even, so is $k - 2$, and since $m$ is a palindrome, the (free) choice of the first $\frac{1}{2}(k - 2)$ of the remaining digits determines the last $\frac{1}{2} (k - 2)$ of the remaining digits, and so there are $2^{(k - 2) / 2}$ binary palindromes of even length $k$.
Similarly, if $k$ is odd, the free choice of the first $\frac{1}{2}(k - 1) $ digits determines the last $\frac{1}{2} (k - 3)$ of the digits. and so there are $2^{(k - 1) / 2}$ binary palindromes of odd length $k$.
Of course, in the special case that $k = 1$ there is just one palindrome, namely $1$ itself (and so the above general formula for odd $k$ extends to this case too).
A: The palindromes of length $2n$ are in bijection with the binary numbers of length $n$ (with leading bit $1$!): write the binary number, followed by its reverse to obtain the palindrome belonging to a number.
The palindromes of length $2n-1$ are also in bijection with the binary numbers of length $n$ (with leading bit $1$!): write the binary number, followed by its reverse, but skip the first bit of the reverse, to obtain the palindrome belinging to a number.
If you sum over all lengths $1,\ldots , 32$, this means that we run over all binary number of lentgth $1$ to $16$ twice. Hence the total is $2\cdot (2^{16}-1)$.
