9
$\begingroup$

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:

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

$\endgroup$
  • 4
    $\begingroup$ 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? ;-) $\endgroup$ – Jyrki Lahtonen Jul 20 '15 at 17:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 20 '15 at 17:26
  • $\begingroup$ 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? $\endgroup$ – Marconius Jul 20 '15 at 17:35
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 20 '15 at 17:39
  • $\begingroup$ What is with this persitent stream of "without induction" questions? They only result in pointless arguments about if that is possible and other inanities... :-/ $\endgroup$ – Mariano Suárez-Álvarez Jul 20 '15 at 22:15
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Winther Jul 21 '15 at 21:41
  • 1
    $\begingroup$ 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! $\endgroup$ – johannesvalks Jul 21 '15 at 21:49
  • 1
    $\begingroup$ @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!). $\endgroup$ – Marconius Jul 21 '15 at 23:25
  • $\begingroup$ @Marconius Ok I will make a re-edit but cannot do this at the moment. I will do it very soon! $\endgroup$ – johannesvalks Jul 21 '15 at 23:49
  • 1
    $\begingroup$ @johannesvalks - Nice proof. The proof was always logical, but was just missing some of the more obvious details. $\endgroup$ – Marconius Jul 22 '15 at 21:55
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ a tip, write $n \in \mathbb{N}$ and not $n \epsilon N$... Try n \in \mathbb{N} $\endgroup$ – johannesvalks Jul 21 '15 at 22:22
  • 1
    $\begingroup$ thanks @johannesvalks,i edited) $\endgroup$ – haqnatural Jul 21 '15 at 22:30
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.