Yes, this can be proven.
The proof is relatively simple but it does require knowledge of Euler's theorem and Euler's totient function (See https://en.wikipedia.org/wiki/Euler's_theorem)
The proof consists of 3 steps and constructs an explicit palindrome for every number n that is not divisible by 10. This will be a possible solution, but by no means the smallest palindrome divisible by n. In fact the constructed palindrome get very large.
1) Find a solution for n=2k or n=5k for every integer k=1,2,3,....
2) Find a solution for any value of n that does not contain a factor 2 or 5
3) Find a solution for any value of n that does contain a factor 2 or 5
