If $ x_1=2$ and $x_{n+1}=2^{x_n}-1$ then $x_n$ divides $2^{x_n}-2$ 
Consider the sequence:
  $$ x_1=2; x_{n+1}=2^{x_n}-1 \text{ for } n\ge 2$$
  Prove that $x_n$ divides $2^{x_n}-2$. 

I tried writing $2^{x_n}-2=2^{2^{x_n-1}-1}-2$ and so on, but that does not help much. Any hints? 
 A: The proof is indeed by induction. For $n = 1$, it is true.
Now suppose that $x_n \mid 2^{x_n} - 2$ holds for $n$.
Write 
$$2^{x_{n+1}} - 2 = 2^{2^{x_n} - 1} - 2 = 2\left( 2^{2^{x_n} - 2} - 1\right).$$
Since $x_{n+1}$ is odd, we have to show that it divides $2^{2^{x_n} - 2} - 1$.
This brings to mind the following factorization for any $z$:
$$z^a - 1 = (z-1)(z^{a-1} + z^{a-2} + \cdots  + 1).$$
In particular,

 if $a \mid b$, then $y^a - 1 \mid y^b - 1$. (Take $b = na$, $z = y^n$).

Then apply the inductive hypothesis that $x_n \mid 2^{x_n} - 2$.
A: Suppose for induction $\ x_n\mid 2^{\large x_n}\!-2.\,$ Then $\ \color{#0a0}{2^{\large x_n}}\! = \color{#0a0}{2\!+\!kx_n}\ $ therefore 
${\rm mod}\,\ x_{n+1}=\color{#c00}{2^{\large x_n}\!-1}\!:\ \ 2^{\large x_{n+1}}= 2^{\large \color{#0a0}{2^{\Large x_n}}-1}  = 2^{\large\color{#0a0}{ 1+kx_n }} = 2(\color{#c00}{2^{\large x_n}})^{\large k}\equiv 2\ $ by $\,\color{#c00}{2^{\large x_n}\equiv 1}$ 
thus $\ x_{n+1}\mid 2^{\large x_{n+1}}\!-2,\ $ i.e. $\ P(n)\,\Rightarrow\, P(n\!+\!1),\,$ so the induction step is true.
