<s>[INST] Prove that $(\sqrt2 − 1)^n, \forall n \in \mathbb{Z^+}$ can be represented as $\sqrt{m} − \sqrt{m−1}$ for some $m \in \mathbb{Z^+}$ (no induction). From the 1994 Canada National Olympiad:

Prove that $(\sqrt2 − 1)^n, \forall n \in \mathbb{Z^+}$ can be represented as $\sqrt{m} − \sqrt{m−1}$ for some $m \in \mathbb{Z^+}$.


I think one solution method is fairly straightforward:


*

*Prove the dual claim that $(\sqrt2 + 1)^n, \forall n \in \mathbb{Z^+}$ can be represented as $\sqrt{m} + \sqrt{m−1}$ for some $m \in \mathbb{Z^+}$, for then $(\sqrt2 − 1)^n = \dfrac{1}{(\sqrt2 + 1)^n} = \dfrac{1}{\sqrt{m} + \sqrt{m−1}} = \sqrt{m} - \sqrt{m−1}$.

*Express $(\sqrt2 + 1)^n = a_n\sqrt2 + b_n$, and formulate a suitable Induction Hypothesis: $IH: (\sqrt2 + 1)^n = a_n\sqrt2 + b_n\text{ with }{b_n}^2-2{a_n}^2 = (-1)^n, n \in \mathbb{Z^+}$.

*Verify $IH$ for $n=1$, and prove the induction step.



Does anyone know of an elegant non-inductive alternative to this method? 
Closed form $a_n, b_n$ are fine as long they are not conjured out of thin air (OEIS etc.).
 [/INST] Step 1
Let us define
$$
\psi(p,q) = p \sqrt{2} + q.
$$
Let us define
$$
\Psi = \big\{ \psi(p,q) | p, q \in \mathbb{Z} \big\}.
$$
We have
$$
\big(p \sqrt{2} + q \big) \big(r \sqrt{2} + s \big)
= \big( p s + q r \big) \sqrt{2} + \big( 2 p r + q s \big).
$$
Therefore

$$
\forall \psi_1, \psi_2 \in \Psi : \psi_1 \psi_2 \in \Psi.
$$

But also

$$
\forall \psi \in \Psi, \forall n \in \mathbb{N} : \psi^n \in \Psi.
$$

Whence for $\psi = \sqrt{2} + 1 \in \Psi$, we get
$$
\forall n \in \mathbb{N} : \big( \sqrt{2} + 1 \big)^n \in \Psi\\
\Downarrow
$$

$$
\exists p, q \mathbb{Z} : \big( \sqrt{2} + 1 \big)^n = p \sqrt{2} + q.
$$

Step 2
Let us define $p_n \in \mathbb{Z}$ and $q_n \in \mathbb{Z}$ such that
$$
\big( \sqrt{2} + 1 \big)^n = p_n \sqrt{2} + q_n.
$$
Thus
$$
p_{n+1} \sqrt{2} + q_{n+1}
= \big( \sqrt{2} + 1 \big) \big( p_n \sqrt{2} + q_n \big)
= \big( p_n + q_n \big) \sqrt{2} + \big( 2 p_n + q_n \big).
$$
So we obtain the recursion relation

$$
\left[
\begin{array}{rcl}
p_0 &=& 0\\\\
q_0 &=& 1\\\\
p_{n+1} &=& p_n + q_n\\\\
q_{n+1} &=& 2 p_n + q_n
\end{array}
\right.
$$

Step 3
Whence
$$
p_1 = p_0 + q_0 = 1
$$
and
$$
p_{n+2} = p_{n+1} + q_{n+1}
= p_{n+1} + 2 p_n + q_n
= p_{n+1} + 2 p_n + p_{n+1} - p_{n}
= 2 p_{n+1} + p_{n}.
$$
Therefore

$$
\left[
\begin{array}{rcl}
p_0 &=& 0\\\\
p_1 &=& 1\\\\
p_{n+2} &=& 2 p_{n+1} + p_{n}\\\\
\hline\\
q_{n} &=& p_{n+1} - p_{n}
\end{array}
\right.
$$

Step 4
The recursion
$$
p_{n+2} = 2 p_{n+1} + p_{n}
$$
is a brother of Fibonacci, as Fibonacci is given by
$F_{n+2} = F_{n+1} + F_{n}$.
We can write
$$
p_{n+2} = 2 p_{n+1} + p_{n}\\
\Downarrow\\
p_{n+2} + \big( \phi - 2 \big) p_{n+1}
= \phi p_{n+1} + p_{n}\\
\Downarrow\\
\phi p_{n+2} + \big( \phi^2 - 2 \phi \big) p_{n+1}
= \phi \big( \phi p_{n+1} + p_{n} \big).
$$
The case
$$
\phi^2 - 2 \phi = 1
$$
yields
$$
\phi p_{n+2} + p_{n+1} = \phi \big( \phi p_{n+1} + p_{n} \big).
$$
So
$$
\phi p_{n+1} + p_{n} = \phi^n \big( \phi p_{1} + p_{0} \big).
$$
As
$$
\phi^2 - 2 \phi = 1 \Rightarrow \phi_\pm = 1 \pm \sqrt{2}
$$
we obtain
$$
\begin{array}{rclc}
\phi_+ \phi_- p_{n+1} + \phi_+ p_{n} &=&
     \phi_+ \phi_-^n \big( \phi_- p_{1} + p_{0} \big)\\
\phi_+ \phi_- p_{n+1} + \phi_- p_{n} &=&
     \phi_- \phi_+^n \big( \phi_+ p_{1} + p_{0} \big)\\
&&&-\\
\hline\\
\big( \phi_+ - \phi_- \big) p_{n} &=&
     \phi_+ \phi_-^n \big( \phi_- p_{1} + p_{0} \big)
   - \phi_- \phi_+^n \big( \phi_+ p_{1} + p_{0} \big)
\end{array}
$$
Whence
$$
p_{n} = - \phi_+ \phi_- \frac{ \phi_+^n - \phi_-^n }{ \phi_+ - \phi_- } p_1
  + \phi_+ \phi_- \frac{ \phi_+^{n-1} - \phi_-^{n-1} }{ \phi_+ - \phi_- } p_0.
$$
As $p_0=0$, $p_1=1$ and $\phi_+ \phi_- = -1$, we obtain

$$
p_{n} = \frac{ \phi_+^n - \phi_-^n }{ \phi_+ - \phi_- } \in \mathbb{Z}.
$$

As
$$
q_n = p_{n+1} - p_n,
$$
we get
$$
q_n = \frac{ \phi_+^{n+1} - \phi_-^{n+1} }{ \phi_+ - \phi_- }
  - \frac{ \phi_+^n - \phi_-^n }{ \phi_+ - \phi_- }
= \frac{ [\phi_+ - 1 ]\phi_+^n - [ \phi_- - 1] \phi_-^n }{ \phi_+ - \phi_- }
= \frac{ \phi_+^n + \phi_-^n }{ \phi_+ - \phi_- } \sqrt{2},
$$
so we obtain

$$
q_{n} = \frac{ \phi_+^n + \phi_-^n }{ \phi_+ - \phi_- } \sqrt{2} \in \mathbb{Z}.
$$

Step 5
Eventually we obtain
$$
( \sqrt{2} + 1 )^n = \frac{ \phi_+^n - \phi_-^n }{ \phi_+ - \phi_- } \sqrt{2}
+ \frac{ \phi_+^n + \phi_-^n }{ \phi_+ - \phi_- } \sqrt{2}.
$$
So
$$
( \sqrt{2} + 1 )^n =
\sqrt{ 2 \left( \frac{ \phi_+^n - \phi_-^n }{ \phi_+ - \phi_- } \right)^2 }
+ \sqrt{ 2 \left( \frac{ \phi_+^n + \phi_-^n }{ \phi_+ - \phi_- } \right)^2 }
$$
Note that
$$
p_{n} = \frac{ \phi_+^n - \phi_-^n }{ \phi_+ - \phi_- }
   \in \mathbb{Z} \Rightarrow
2 \left( \frac{ \phi_+^n - \phi_-^n }{ \phi_+ - \phi_- } \right)^2
   \in \mathbb{Z},
$$
Now comes the fun part:
$$
2 \left( \frac{ \phi_+^n + \phi_-^n }{ \phi_+ - \phi_- } \right)^2
= 2 \left( \frac{ \phi_+^n - \phi_-^n }{ \phi_+ - \phi_- } \right)^2
+ 8 \frac{ \big( \phi_+ \phi_- \big)^n  }{ \big( \phi_+ - \phi_- \big)^2 },
$$
and as $\phi_+ \phi_- = -1$ and $\phi_+ - \phi_- = 2 \sqrt{2}$,
we get
$$
2 \left( \frac{ \phi_+^n + \phi_-^n }{ \phi_+ - \phi_- } \right)^2
= 2 \left( \frac{ \phi_+^n - \phi_-^n }{ \phi_+ - \phi_- } \right)^2
+ (-1)^n.
$$
Let
$$
m = 2 \left( \frac{ \phi_+^n - \phi_-^n }{ \phi_+ - \phi_- } \right)^2
 + \frac{1 + (-1)^n}{2}.
$$
Whence

$$
( \sqrt{2} + 1 )^n = \sqrt{m} + \sqrt{m-1}.
$$

Step 6
Note that
$$
( \sqrt{2} + 1 ) ( \sqrt{2} - 1 ) = 1
$$
and
$$
( \sqrt{m} + \sqrt{m-1} ) ( \sqrt{m} - \sqrt{m-1} ) = 1,
$$
then
$$
( \sqrt{2} - 1 )^n
= \frac{1}{ ( \sqrt{2} + 1 )^n }
= \frac{1}{ \sqrt{m} + \sqrt{m-1} }
= \sqrt{m} - \sqrt{m-1}.
$$
Whence

$$
( \sqrt{2} - 1 )^n = \sqrt{m} - \sqrt{m-1}.
$$

Conclusion

$$
( \sqrt{2} \pm 1 )^n = \sqrt{m} \pm \sqrt{m-1},
$$
  where
  $$
m = 2 \left( \frac{ \phi_+^n - \phi_-^n }{ \phi_+ - \phi_- } \right)^2
 + \frac{1 + (-1)^n}{2},
$$
  and
  $$
\phi_\pm = 1 \pm \sqrt{2}.
$$

</s>