# 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).

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:

1. 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}$.
2. 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^+}$.
3. 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.).

• I'm not sure that you like this, but... If $(1+\sqrt2)^n=b_n+a_n\sqrt2$, then by binomial formula $(1-\sqrt2)^n=b_n-a_n\sqrt2$. Therefore (drums, please) $$b_n=\frac12\left[(1+\sqrt2)^n+(1-\sqrt2)^n\right],$$ and $$a_n=\frac1{2\sqrt2}\left[(1+\sqrt2)^n-(1-\sqrt2)^n\right].$$ Does that closed formula for $b_n$ and $a_n$ help? ;-) – Jyrki Lahtonen Jul 20 '15 at 17:20
• You do realize that $\sqrt{x}-\sqrt{x-1}$ is a decreasing function in the interval $x\in[1,\infty)$. Meaning that $m$ is determined uniquely. Therefore all solutions lead to those $(a_n,b_n)$ pairs. If this is what you wanted to hear, I can try and flesh that out as an answer. If you wanted to know something else about this problem, please specify. – Jyrki Lahtonen Jul 20 '15 at 17:26
• The closed form for $a_n, b_n$ is good. The rest is just number-crunching then. As far as your other remark goes, what exactly do you mean by $m$ being uniquely determined? – Marconius Jul 20 '15 at 17:35
• I meant that to each $n$ there is exactly one $m$ such that the identity holds. I was just catering for the possibility that you felt may be there could be alternatives. – Jyrki Lahtonen Jul 20 '15 at 17:39
• What is with this persitent stream of "without induction" questions? They only result in pointless arguments about if that is possible and other inanities... :-/ – Mariano Suárez-Álvarez Jul 20 '15 at 22:15

# 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}.$$

• This seems to work, but the answer could do with some more comments so it's clear that $m$ is indeed a whole number (which is not so easy to see now). This seems to follow from $m = q_n^2 + \frac{1+(-1)^n}{2}$ + recurence relation + $q_1$ being an integer. Could be useful to add explanations like this. – Winther Jul 21 '15 at 21:41
• I have written this post fast. Perhaps I need to revise it and add more comments. That $m$ is an integer follows from $m=2 p_n^2$, and $p_n$ is an integer follows from the recursion relation. But thanks for the comment! – johannesvalks Jul 21 '15 at 21:49
• @johannesvalks - Just add those remarks and I will definitely accept this answer. I see what you mean about "brother of Fibonacci": in F.S. you have terms $a,b,a+b,a+2b$, whereas if you write a series with $p,q$ alternating, here you have terms $a,b,a+b,2a+b$ (only the 2 has shifted!). – Marconius Jul 21 '15 at 23:25
• @Marconius Ok I will make a re-edit but cannot do this at the moment. I will do it very soon! – johannesvalks Jul 21 '15 at 23:49
• @johannesvalks - Nice proof. The proof was always logical, but was just missing some of the more obvious details. – Marconius Jul 22 '15 at 21:55

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 tip, write $n \in \mathbb{N}$ and not $n \epsilon N$... Try n \in \mathbb{N} – johannesvalks Jul 21 '15 at 22:22
• thanks @johannesvalks,i edited) – haqnatural Jul 21 '15 at 22:30

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}.$$