Proof for divisibility rule for palindromic integers of even length I am studying for a test and came across this in my practice materials. I can prove it simply for some individual cases, but I don't know where to start to prove the full statement.

Prove that every palindromic integer in base $k$ with an even number of digits is divisible by $k+1$.

 A: Do you know that if $m$ is odd then $x+1$ is a factor of $x^m+1$? Do you see how to use this to answer the question?
A: You could apply the generalized divisibility test for 11: a base $k$ number is divisible by $k+1$ iff the sum of its odd digits minus the sum of its even digits is divisible by $k+1$.  (In particular, if a number is palindromic and has an even number of digits, it's easy to see that its odd and even digits sum to the same number.)
A: HINT  $\rm\ \ mod\ \ x+1:\ \ f(x) + x^{n+1}\:(x^n\ f(1/x))\ \equiv\ f(-1) - f(-1)\:\equiv\: 0$  
Remark $\ \ $ It is simple to verify that $\rm\ x^n\ f(1/x)\ $ is the reversal of a polynomial $\rm\:f\:$ of degree $\rm\:n\:,\:$ therefore the above is the general palindromic polynomial with even number of coefficients.  
See also the closely related question.
A: The second claim written below will prove your result. In general, you can mimic the divisibility tests for $9$ and $11$. $9$ and $11$ have simple divisibility rules since we deal with decimal number system i.e. base $10$. You can develop divisibility rules for $k$, on a similar note, by expressing it either in base $k+1$ (or) base $k-1$.
Claim 1:
One possible divisibility for a number '$a$' to be divided by '$n$' is as follows. Express the number '$a$' in base '$n+1$'. Let '$s$' denote the sum of digits of '$a$' expressed in base '$n+1$'. 
Now $n|a \iff n|s$. More generally, $a \equiv s \pmod{n}$
Example:
Before setting to prove this, we will see an example of this. Say we want to check if $13|611$. Express $611$ in base $14$.
$611 = 3 \times 14^2 + 1 \times 14^1 + 9 \times 14^0 = (319)_{14}$
where $(319)_{14}$ denotes that the decimal number $611$ expressed in base $14$.
The sum of the digits $s = 3 + 1 + 9 = 13$. Clearly, $13|13$. Hence, $13|611$, which is indeed true since $611 = 13 \times 47$.
Proof:
The proof for this claim writes itself out.
Let $a = (a_ma_{m-1} \ldots a_0)_{n+1}$, where $a_i$ are the digits of '$a$' in the base '$n+1$'.
$a = a_m \times (n+1)^m + a_{m-1} \times (n+1)^{m-1} + \cdots + a_0$
Now, note that
$$n+1 \equiv 1 \pmod n$$
$$(n+1)^k \equiv 1 \pmod n$$
$$a_k \times (n+1)^k  \equiv a_k \pmod n$$
$$a = a_m \times (n+1)^m + a_{m-1} \times (n+1)^{m-1} + \cdots + a_0$$
$$\equiv (a_m + a_{m-1} \cdots + a_0) \pmod n$$
$$a \equiv s \pmod n$$
Hence proved.
Claim 2:
Another possible divisibility rule for a number '$a$' to be divided by '$n$' is as follows. Express the number '$a$' in base '$n-1$'. Let '$s$' denote the alternating sum of digits of '$a$' expressed in base '$n-1$' i.e. if $a = (a_ma_{m-1} \ldots a_0)_{n-1}$, $s = a_0 - a_1 + a_2 - \cdots + (-1)^{m-1}a_{m-1} + (-1)^m a_m$
Now $n|a$ if and only $n|s$. More generally, $a \equiv s \pmod{n}$
Example:
Before setting to prove this, we will see an example of this. Say we want to check if $13|611$. Express $611$ in base $12$.
$611 = 4 \times 12^2 + 2 \times 12^1 + B \times 12^0 = (42B)_{12}$
where $(42B)_{14}$ denotes that the decimal number $611$ expressed in base $12$, $A$ stands for the tenth digit and $B$ stands for the eleventh digit.
The alternating sum of the digits $s = B_{12} - 2 + 4 = 13$. Clearly, $13|13$. Hence, $13|611$, which is indeed true since $611 = 13 \times 47$.
Proof:
The proof for this claim writes itself out just like the one above.
Let $a = (a_ma_{m-1} \ldots a_0)_{n+1}$, where $a_i$ are the digits of '$a$' in the base '$n-1$'.
$a = a_m \times (n-1)^m + a_{m-1} \times (n-1)^{m-1} + \cdots + a_0$
Now, note that
$$n-1 \equiv (-1) \pmod n$$
$$(n-1)^k \equiv (-1)^k \pmod n$$
$$a_k \times (n-1)^k \equiv (-1)^k a_k \pmod n$$
$$a = a_m \times (n-1)^m + a_{m-1} \times (n-1)^{m-1} + \cdots + a_0$$
$$a \equiv ((-1)^m a_m + (-1)^{m-1} a_{m-1} \cdots + a_0) \pmod n$$
$$a \equiv s \pmod n$$
Hence proved.
