Palindromes in multiple bases

You were not able to prove it because it's not true. The OEIS has the first 17 of them as sequence A060792, and it is not known whether any more exist.

Sadly, $6643_{10}=1100111110011_2=100010001_3$ is a palindrome in bases $2$ and $3$. $1422773$ and $5415589$ also satisfy the property.

Having "magically" found counterexamples, let us explore how we could find at least the first one. Do we really face the specter of having to run thousands of trials? Not if we apply a little ingenuity.

A base 2 palindrome must be odd or else the reverse base 2 representation has an initial zero, not allowed. Then the base 3 representation, being odd, must have an odd sum of digits (c.f. the base 10 test for a multiple of 3). The only base-3 palindromic representations matching this condition have the form $a1a*$ where $a$ is a base 3 representation with no initial zeroes and $a*$ is obtained by reversing the digits of $a$ ($a*$ keeps any initial zeroes corresponding to the terminal zeroes of $a$). Note that not allowing any initial zeroes in $a$ automatically enables us to dodge multiples of 3.

Let us select $a=110_3$ as an example. Keeping the terminal zero as an initial zero of $a*$ gives $a*=011_3$ and thus the odd base 3 palindrome $1101011_3$.

Now we check whether this is palindromic in base 2. A convenient way to do this is to first convert to base 4. Treat the base 3 representation as a polynomial in which the digits, including zeroes, are successive coefficients of decreasing powers of $x$ and evaluate at $x=3$ using synthetic division. In base 4 you use the "multiplication facts" $3×2=12$ and $3×3=21$ to carry out the arithmetic. Applying this technique to $1101011_3$:

$$1=1$$ $$1×3+1=10$$ $$10×3+0=30$$ $$30×3+1=211$$ $$211×3+0=1233$$ $$1233×3+1=11032$$ $$11032×3+1=33223$$

So $1101011_3=33223_4$, and converting each base 4 digit to the appropriate pair of bits then gives $1111101011_2$.

This fails to be a palindrome. A systematic trial would start with $a=1$ and proceed to $a=2, a=10_3$, etc. The first 26 trials fail, on trial 27 the reader can verify that $a=1000_3$ gives, properly, $100010001_3=1213303_4=1100111110011_2$. This is $6643_{10}$.