By induction on $n$, we prove that $x_n$ divides $x_{n+1}$ and $x_n^2$ divides $x_{n-1}x_{n+1}$. First note that since $k$ is even, each of the $x_n$ is odd. For $n=2$ we want to prove that both $k+1$ and $(k+1)^2$ divide $k^{k+1} + 1.$ clearly, we only have to prove for the second. But, since $k+1$ is odd, we have $k^{k+1} + 1 = (k+1)(k^k - k^{k-1} + \cdots + 1)$. Moreover, $k = -1 \mod [k+1]$ then, since $k$ is even : $k^k - k^{k-1} + \cdots + 1 = (-1)^k - (-1)^{k-1} + \cdots + 1 = 1 + 1 +\cdots + 1 = k+1 = 0 \mod [k+1]$, and we are done. Now assume that for some $n$ we have $x_n = a_{n-1}x_{n-1}$ and $x_{n-1}^2$ divides $x_nx_{n-2}.$ Note that $a_{n-1}$ is odd. Then : $x_{n+1} = k^{x_n} + 1 = k^{a_{n-1}x_{n-1}} + 1 = (k^{x_{n-1}} + 1)(k^{x_{n-1}(a_{n-1}-1)} - k^{x_{n-1}(a_{n-1}-2)} + \cdots + 1) = x_n(k^{x_{n-1}(a_{n-1}-1)} - k^{x_{n-1}(a_{n-1}-2)} + \cdots + 1)$. Then $x_n$ divides $x_{n+1}.$ Moreover $k^{x_{n-1}} = -1 \mod [x_n]$ then, since $a_{n-1}$ is odd : $k^{x_{n-1}(a_{n-1}-1)} - k^{x_{n-1}(a_{n-1}-2)} + \cdots + 1 = (-1)^{a_{n-1}-1} - (-1)^{a_{n-1}-2} + + \cdots + 1 = a_{n-1} \mod [x_n]$. Thus $x_{n-1} (k^{x_{n-1}(a_{n-1}-1)} - k^{x_{n-1}(a_{n-1}-2)} + \cdots + 1)= x_{n-1}a_{n-1} = x_n = 0 \mod [x_n]$ so that $x_{n-1}x_{n+1}$ is divisible by $x_n^2$, which ends the induction step. Pierre.

Thanks, pierre. Induction works most of the times in series questions!!!