<s>[INST] Minimum values of the sequence $\{n\sqrt{2}\}$ I have been studying the sequence
$$\{n\sqrt{2}\}$$
where $\{x\}:= x-\lfloor x\rfloor$ is the "fractional part" function. I am particularly interested in the values of $n$ for which $\{n\sqrt{2}\}$ has an extremely small value - that is, when $n\sqrt 2$ is extremely close to (but greater than) its nearest integer. Of course, for integer $n$, this always takes on values between (but never including) $0$ and $1$.
I have defined the sequence $M_n$ as follows:


*

*$M_1=1$

*$M_{n+1}$ is the smallest positive integer such that $\{M_{n+1}\sqrt 2\}\lt \{M_n\sqrt 2\}$


The first few terms of this sequence are
$$1,3,5,17,29,99,169,...$$
And after a quick trip to the OEIS, I have found that this sequence is equal to OEIS entry A079496, as written in the comments. It also provides the recurrence
$$a_0=a_1=1$$
$$a_{2n+1}=2a_{2n}-a_{2n-1}$$
$$a_{2n}=4a_{2n-1}-a_{2n-2}$$
How can I prove that the sequence $M_n$ satisfies this recurrence, using the definition I wrote for $M_n$?
Thanks!
EDIT: Here is the closed-form explicit formula for $a_n$, for anyone who wants to know:
$$a_{2n}=\frac{(3+2\sqrt 2)^n+(3-2\sqrt 2)^n}{2}$$
$$a_{2n+1}=\frac{(1+\sqrt 2)(3+2\sqrt 2)^n-(1-\sqrt 2)(3-2\sqrt 2)^n}{2\sqrt 2}$$
 [/INST] This is about Pell type equations. Absolutely complete detail would be a bit long. I have posted many times about solving $x^2 - n y^2 = T,$ where $T$ is some target number, and $n$ is positive not a square.
Your sequence is this: given positive integer $x,$ let $v = \lfloor x \sqrt 2 \rfloor.$ Your numbers will be
$$ 2 x^2 - v^2 \in \{ 1,2  \}.  $$
Furthermore, the ratios of consecutive terms are bounded: if $w$ is a number with worse $2 w^2 - w_0^2,$ where $w_0 = \lfloor w \sqrt 2 \rfloor,$ then there is one of your numbers $t$ with $t > w/(2 + \sqrt 2).$ 
Alright, the positive values of $2x^2 - y^2$ are $1,2,4,7,8,9, 14 \ldots$ where we are allowing common factors of $x,y.$ 
If $2x^2 - v^2 = 4,$ then both $x,v$ are even, we can take $t = x/2,$ and the fractional part of $t \sqrt 2$ is half the fractional part of $x \sqrt 2,$ meaning $x$ cannot be part of your $M$ sequence. Now that I think of it, the same applies to any number divisible by $4$ or by $9.$ As a result, if we calculated $2x^2 - v^2 = 7$ as a special case (we know how to find all representations) we could then continue with $2 x^2 - v^2 \geq 14.$
It appears we need just the one special case. After this, we may take
$$ 2 x^2 - v^2 \geq 7,  $$ with
$$ \{ x \sqrt 2 \}  \geq \frac{7}{x \sqrt 2 + v} \approx \frac{7}{2x \sqrt 2 }\approx \frac{2.4748737}{x  }  .  $$
$$ t > \frac{x}{2 + \sqrt 2},  $$
$$  2 t^2 - w^2  \in \{ 1,2  \}.  $$
$$ (t \sqrt 2 - w)(t \sqrt 2 + w) \leq 2.  $$
$$ t \sqrt 2 - w \leq \frac{2}{t \sqrt 2 + w}.  $$
$$ \{ t \sqrt 2 \}  \leq \frac{2}{t \sqrt 2 + w} \approx \frac{2}{2t \sqrt 2 }  \approx \frac{1}{t \sqrt 2 } < \frac{2 + \sqrt 2}{x \sqrt 2 } = \frac{1 + \sqrt 2}{x  } \approx   \frac{2.1421356}{x  } .  $$
This is smaller than
$$ \{ x \sqrt 2 \}  \geq \frac{7}{x \sqrt 2 + v} \approx \frac{7}{2x \sqrt 2 }\approx \frac{2.4748737}{x  }  .  $$
A more careful analysis is possible, correction terms all over, but the heart of it is the observation that the floor of $t \sqrt 2$ is extremely close to the real number itself, when $0 < 2t^2 - w^2 \leq 2$. 
Here is the Conway topograph for the negative of your form, $x^2 - 2 y^2.$ Your numbers show up representing negative number, (4,3) gives $-2$, then (7,5) gives $-1,$ then (24,17) give $-2,$ (41,29) gives $-1$
Let's see, it will take an hour or so, but I can draw a topograph for $2x^2 - v^2$ that shows numbers represented up to $17,$ as numbers such as $4,8,9$ are not squarefree, and are not primitively represented  (we get $\gcd(x,v) \neq 1$). Will, 9:19 Pacific time
Done. Note that the green coordinate pairs have a motion that gives the same value of $2x^2 - y^2,$ namely
$$ (x,y) \mapsto (3x+2y, 4x+3y).   $$ For example, $ (1,1) \mapsto (5, 7 )   $ and  $ (3,4) \mapsto (17, 24 ).   $
Let's see, Cayley Hamilton for the coefficient matrix
$$
\left(
\begin{array}{cc}
3 & 2 \\
4 & 3
\end{array}
\right)
$$
gives the linear recurrence, 
$$x_{n+4} = 6 x_{n+2} - x_n  $$
if we combine the $x$ values in a single list. We need to separate odd index and even index because we are combining $2x^2-v^2 = 1$ and $2x^2 - v^2 = 2$ in one list of $x$ values

There is a book that Allen Hatcher makes available online, here is his diagram for $x^2 - 2 y^2,$ but without the green coordinates that I like to include. The topograph diagram was introduced by J. H. Conway 

</s>