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.).
 A: 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}.
$$

A: If we look it as general such as:for every $n,m\in \mathbb{N}$ have $\quad \exists k\in \mathbb{N}\quad \\ \\ $ 

$$ \left( \sqrt { m } -\sqrt { m-1 }  \right) ^{ n }=\sqrt { k } +\sqrt { k-1 } $$ using binomial formula,we will get

$$\left( \sqrt { m } \pm \sqrt { m-1 }  \right) ^{ n }=\sum _{ i=0 }^{ n }{ { C }_{ n }^{ i }\left( \sqrt { m }  \right) ^{ n-i }\left( \pm \sqrt { m-1 }  \right) ^{ i } } \\ $$
in case $n=2j\left( j\in \mathbb{N} \right)$ it we will get:
$$\left( \sqrt { m } \pm \sqrt { m-1 }  \right) ^{ n }=\sum _{ i=0 }^{ j }{ { C }_{ n }^{ 2i }\left( \sqrt { m }  \right) ^{ 2j-2i }\left( \sqrt { m-1 }  \right) ^{ 2i } } \pm $$ $$\pm \sum _{ i=1 }^{ j }{ { C }_{ n }^{ 2i-1 }\left( \sqrt { m }  \right) ^{ 2j-2i+1 }\left( \sqrt { m-1 }  \right) ^{ 2i-1 }= } $$
$$ \\ \\ =\sum _{ i=0 }^{ j }{ { C }_{ n }^{ 2i }{ m }^{ j-i }\left( m-1 \right) ^{ i }\pm \sqrt { m\left( m-1 \right)  } \sum _{ i=1 }^{ j }{ { C }_{ n }^{ 2i-1 } }  } { m }^{ j-i }\left( m-1 \right) ^{ i-1 }=a\pm b\sqrt { m\left( m-1 \right)  } \\ $$ 
where $a,b\in \mathbb{Z}^{ + }$ 
and in case $n=2j-1\left( j\in \mathbb{N} \right) $ we will get :
$$\left( \sqrt { m } \pm \sqrt { m-1 }  \right) ^{ n }=\sum _{ i=0 }^{ j-1 }{ { C }_{ n }^{ 2i }\left( \sqrt { m }  \right) ^{ 2j-1-2i }\left( \sqrt { m-1 }  \right) ^{ 2i } } \pm $$
$$ \pm \sum _{ i=1 }^{ j }{ { C }_{ n }^{ 2i-1 }\left( \sqrt { m }  \right) ^{ 2j-2i }\left( \sqrt { m-1 }  \right) ^{ 2i-1 }= } $$  $$\\ \\ =\sqrt { m } \sum _{ i=0 }^{ j-1 }{ { C }_{ n }^{ 2j }{ m }^{ j-i-1 }\left( m-1 \right) ^{ i }\pm \sqrt { m-1 } \sum _{ i=1 }^{ j }{ { C }_{ n }^{ 2i-1 } }  } { m }^{ j-i }\left( m-1 \right) ^{ i-1 }=c\sqrt { m } \pm d\sqrt { m-1 } $$ where $c,d\in \mathbb{Z }^{ + }$  in both case we have equitions
$$\left( \sqrt { m } \pm \sqrt { m-1 }  \right) ^{ n }=\sqrt { k } \pm \sqrt { l } $$  for $k,l\in \mathbb{Z}^{ + }$
and
$$k-l=\left( \sqrt { k } +\sqrt { l }  \right) \left( \sqrt { k } -\sqrt { l }  \right) =\left( \sqrt { m } +\sqrt { m-1 }  \right) ^{ n }\left( \sqrt { m } -\sqrt { m-1 }  \right) ^{ n }=\\ =\left( \left( \sqrt { m }  \right) ^{ 2 }-\left( \sqrt { m-1 }  \right) ^{ 2 } \right) ^{ n }=1\\ $$
hence 
$$l=k-1$$ and $$\\ \left( \sqrt { m } +\sqrt { m-1 }  \right) ^{ n }=\sqrt { k } +\sqrt { k-1 } $$
as you can see your problem part of it (in case  m=2)
i hope you will understand,i tried to write few words,because of my poor english
A: While working on this problem, I noted a general method.
Therefore I added another post to explain this general method.

Definitions
Note that
$$
\big( x \pm y \big)^n =
      \frac{ \big( x + y \big)^n + \big( x - y \big)^n}{2}
  \pm \frac{ \big( x + y \big)^n - \big( x - y \big)^n}{2}.
$$
Let us define
$$
\left[
\begin{array}{rcl}
c_n(x,y) &=& \displaystyle \frac{ \big(x+y\big)^n + \big(x-y\big)^n}{2}\\\\
s_n(x,y) &=& \displaystyle \frac{ \big(x+y\big)^n - \big(x-y\big)^n}{2}
\end{array}
\right.
$$
so we can write

$$
\big( x \pm y \big)^n = c_n(x,y) \pm s_n(x,y).
$$

Property
From the definitions of $c_n(x,y)$ and $s_n(x,y)$ follows
$$
c^2_n(x,y) - s^2_n(x,y) = \big( x^2 - y^2 \big)^n.
$$
And a special case is given by

$$
x^2 - y^2 = 1 \Longrightarrow c^2_n(x,y) - s^2_n(x,y) = 1
$$

Special case $x^2 - y^2 = 1$
For the special case $x^2 - y^2 = 1$ we can write
$$
\left[
\begin{array}{rcl}
x &=& \displaystyle \sqrt{1 + \kappa^2}\\\\
y &=& \kappa
\end{array}
\right.
$$
whence
$$
\Big( \sqrt{1 + \kappa^2} \pm \kappa \Big)^n =
     \sqrt{ c^2_n\Big( \sqrt{1 + \kappa^2}, \kappa \Big) }
 \pm \sqrt{ c^2_n\Big( \sqrt{1 + \kappa^2}, \kappa \Big) - 1 }
$$
Therefore

$$
\mu = c^2_n\Big( \sqrt{1 + \kappa^2}, \kappa \Big)
\Longrightarrow
\Big( \sqrt{1 + \kappa^2} \pm \kappa \Big)^n =
     \sqrt{ \mu }
 \pm \sqrt{ \mu - 1 }
$$

Property of $c^2_n(x,y)$
From the definition of $c_n(x,y)$ follows
$$
c_{n}(x,y) = \sum_{\imath=0}^{n} \binom{n}{\imath} \frac{1 + (-1)^\imath}{2}
x^{n-\imath} y^{\imath}.
$$
Whence
$$
\begin{array}{rclcrcl}
n &=& 2 o &:&
  c^2_{2 o}(x,y) &=& \displaystyle
    \left\{ \sum_{\imath=0}^{2 o} \binom{2 o}{\imath}
      \frac{1 + (-1)^\imath}{2} x^{2o - \imath} y^{\imath} \right\}^2\\
&&&&&=& \displaystyle
    \left\{ \sum_{\jmath=0}^{o} \binom{2 o}{2\jmath}
      \big(x^2\big)^{o - \jmath} \big(y^2\big)^{\jmath} \right\}^2.\\\\
n &=& 2 o + 1 &:&
  c^2_{2 o + 1}(x,y) &=& \displaystyle
    \left\{ \sum_{\imath=0}^{2 o + 1} \binom{2 o + 1}{\imath}
      \frac{1 + (-1)^\imath}{2} x^{2 o + 1 -\imath} y^{\imath} \right\}^2\\
&&&&&=& \displaystyle
    x^2 \left\{ \sum_{\jmath=0}^{o} \binom{2 o + 1}{2\jmath}
      \big(x^2\big)^{o - \jmath} \big(y^2\big)^{\jmath} \right\}^2.
\end{array}
$$
Eventually we obtain

$$
c^2_n(x,y) = F(x^2,y^2).
$$

The ring $\mathcal{R}$
Let $\mathcal{R}$ be a ring.
A polynomial $P_\mathcal{R}(x,y)$ is defined as
$$
\forall v,w \in \mathbb{N}, r_{vw} \in \mathcal{R} :
  \mathcal{R} \times \mathcal{R} \ni (x,y) \mapsto
    P_\mathcal{R}(x,y) =\sum_{v,w} r_{vw} x^v y^w \in \mathcal{R}. 
$$
Let $\mathcal{R}$ be a ring, such that $\mathbb{N} \subset \mathcal{R}$.
Then it is clear that

$$
\mathcal{R} \times \mathcal{R} \ni (x^2,y^2) \mapsto
    c^2_n(x,y) = P_\mathcal{R}(x^2,y^2) \in \mathcal{R}.
$$

Conclusion
Consequently we find

Let $\mathcal{R}$ be a ring, such that $\mathbb{N} \subset \mathcal{R}$,
  then
  $$
\forall k \in \mathcal{R}, n \in \mathbb{N}:
  ( \sqrt{ 1 + k^2 } \pm k )^n = \sqrt{m} \pm \sqrt{m-1},
$$
  where
  $$
m = c^2_n\big( \sqrt{ 1 + k^2 }, k \big) =
    P_\mathcal{R}(1 + k^2,k^2) \in \mathcal{R}.
$$
  Note that
  $$
\forall k \ni \mathcal{R} : m = \left( \frac{ \big( \sqrt{ 1 + k^2 } + k \big)^n
  + \big( \sqrt{ 1 + k^2 } - k \big)^n }{2} \right)^2 \in \mathcal{R}.
$$

The problem
Consider the ring $\mathbb{Z}$.
It is clear that $\mathbb{N} \subset \mathbb{Z}$.
Whence

$$
\forall k \in \mathbb{Z}, n \in \mathbb{N}:
  ( \sqrt{ 1 + k^2 } \pm k )^n = \sqrt{m} \pm \sqrt{m-1},
$$
  where
  $$
\forall k \ni \mathbb{Z} : m = \left( \frac{ \big( \sqrt{ 1 + k^2 } + k \big)^n
  + \big( \sqrt{ 1 + k^2 } - k \big)^n }{2} \right)^2 \in \mathbb{Z}.
$$

The problem - case $k=1$

$$
( \sqrt{ 2 } \pm 1 )^n = \sqrt{m} \pm \sqrt{m-1},
$$
  where
  $$
m = \left( \frac{ \big( \sqrt{ 2 } + 1 \big)^n
  + \big( \sqrt{ 2 } - 1 \big)^n }{2} \right)^2 \in \mathbb{Z}.
$$

