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

A: Continued Fraction Approximations
The continued fraction for $\sqrt2$ is
$$
\sqrt2=1+\cfrac1{2+\cfrac1{2+\cfrac1{2+\dots}}}\tag1
$$
The approximants alternate between a bit too high and a bit too low, but we always have
$$
\left|\,\frac{p_n}{q_n}-\sqrt2\,\right|\le\frac1{2q_n^2}\tag2
$$
because of the continued fraction, we have
$$
p_n=2p_{n-1}+p_{n-2}\quad\text{and}\quad q_n=2q_{n-1}+q_{n-2}\tag3
$$
starting with $\frac11$ (low) and $\frac32$ (high). The first several continued fraction approximants are
$$
\frac11,\frac32,\frac75,\frac{17}{12},\frac{41}{29},\frac{99}{70},\dots\tag4
$$

Low Approximations
We want to choose the approximations that are a bit low so that $q_n\sqrt2\gt p_n$. Then
$$
\left\{q_n\sqrt2\right\}=q_n\sqrt2-p_n\le\frac1{2q_n}\tag5
$$
Since we only want the low approximations, we need to modify the recursion in $(3)$ to skip the high approximations. To that end, we have
$$
p_n=6p_{n-2}-p_{n-4}\quad\text{and}\quad q_n=6q_{n-2}-q_{n-4}\tag6
$$
starting with $\frac11$ and $\frac75$. The first several low continued fraction approximations are
$$
\frac11,\frac75,\frac{41}{29},\frac{239}{169},\frac{1393}{985},\dots\tag7
$$
We can also make some close low approximations by looking at twice the reciprocals of the high approximations.  These will follow the recursion in $(6)$:
$$
\frac43,\frac{24}{17},\frac{140}{99},\frac{816}{577},\dots\tag8
$$
The denominators of these two sequences, which follow the recursion in $(6)$, cover all of the elements of the sequences in the question.

Combined Sequence
The combined sequence follows the recursion
$$
a_n=6a_{n-2}-a_{n-4}
$$
and starts out
$$
1,3,5,17,\dots
$$
A: Summary of solution : the originality of your question consists in its use of 
the floor function to round, when most of the classical results on continued fractions use
the nearest integer function. The idea is to reduce the former to the latter. 
Details :
Let $M_n,a_n$ be as in the OP. Our goal is to show that 
$$
M_n=a_n \tag{1}
$$
As a convenience, let us use the "normalized" number $\alpha=\sqrt{2}-1$ (which is in the unit interval) rather than $\sqrt{2}$ itself.
It will suffice to show :
$$
\lbrace q\alpha \rbrace \geq \lbrace a_n\alpha \rbrace 
\textrm{ for } 0 \lt q \lt a_{n+1} \tag{2}
$$
We will use a sequence closely related to the continued fraction expansion of $\alpha$, namely $g_n=\frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$. Note that $(g_n)$ satisfies 
$g_0=0,g_1=1$ and $g_{n+2}-2g_{n+1}+g_n=0$, so its values (after $g_1$) are positive integers. The following properties are easy to show by a direct computation or by induction :
$(i)$ $g_ng_{n+2}-g_{n+1}^2=(-1)^{n+1}$
$(ii)$ $a_n=g_n$ when $n$ is odd
$(iii)$ $a_n=g_{n+1}-g_n$ when $n$ is even 
$(iv)$ $\frac{g_n-g_{n+1}\alpha}{g_{n+1}-g_{n+2}\alpha}=1-\sqrt{2}$
$(v)$ $\frac{a_{n+2}\alpha -(g_{n+2}-g_{n+1})}{a_n\alpha -(g_n-g_{n-1})}=3-2\sqrt{2}$,
when $n$ is even.
The following lemma is a very classic continued fraction inequality :
LEMMA. Let $p,q$ be integers with $0 \lt q \lt g_{n+2}$. Then $|p-q\alpha| \geq |g_n-g_{n+1}\alpha|$. Further, if  $(p,q)\neq (g_n,g_{n+1})$, the inequality can be strenghtened to $|p-q\alpha| \geq |g_n-g_{n+1}\alpha|+|g_{n+1}-g_{n+2}\alpha|$.
Proof of lemma. By (i),  the matrix $\left(\begin{matrix} g_n & g_{n+1} \\ g_{n+1} & g_{n+2} \end{matrix}\right)$ is unimodular. It follows that there are integers $u,v$ such that $p=g_n u+g_{n+1}v$ and $q=g_{n+1}u+g_{n+2}v$. I claim that $uv\leq 0$ ; otherwise, $g_{n+1}u$ and $g_{n+2}v$ would both be nonzero and have the same sign, forcing $|q| = |g_{n+1}u|+|g_{n+2}v| \geq |g_{n+2}|$ which is impossible. So $uv\leq 0$, and also
$$
p-q\alpha= u(g_n-g_{n+1}\alpha) + v (g_{n+1}-g_{n+2}\alpha) \tag{3}
$$
The numbers $u(g_n-g_{n+1}\alpha)$ and $v(g_{n+1}-g_{n+2}\alpha)$ have the same sign, so
$$
|p-q\alpha|= |u(g_n-g_{n+1}\alpha)| + |v (g_{n+1}-g_{n+2}\alpha)| \tag{4}
$$
Note that $u\neq 0$ because of $q=g_{n+1}u+g_{n+2}v$ and $|q|<g_{n+2}$. So $|u|\geq 1$ and the first inequality follows. If equality holds, we must have $|u|=1$ and $v=0$, from which we easily deduce $(p,q)=(g_n,g_{n+1})$. Suppose now that $(p,q)\neq (g_n,g_{n+1})$. If $|u|\geq 2$, then from (4) we deduce $|p-q\alpha| \geq 2|g_n-g_{n+1}\alpha|$. By (iv), the second inequality holds in this case.
Otherwise $u=1$ and from the reasoning above we have $v\neq 0$, so $|v|\geq 1$ and from (4) again we deduce $|p-q\alpha| \geq |g_n-g_{n+1}\alpha|+|g_{n+1}-g_{n+2}\alpha|$, which finishes the proof of the lemma.
Let us now deduce (2) from the lemma. Suppose first that $n$ is odd. By $(ii)$, $\lbrace a_n\alpha \rbrace=\lbrace g_n\alpha \rbrace=g_{n+1}\alpha-g_n$ by lemma, (iv) and the fact that $g_{n+1}\alpha-g_n >0$.
The lemma also shows that $\lbrace q \alpha \rbrace \geq \lbrace a_n \alpha \rbrace$
for $0 \lt q \lt g_{n+2}=a_{n+2}$, as wished.
Suppose now that $n$ is even. Using the lemma with $n-1$ in place of $n$, we have that for any $0 \lt q \lt g_{n+1}=a_{n+1}$ and $(p,q)\neq (g_{n-1},g_n)$, then 
$$\begin{array}{lcl}
|p-q\alpha| &\geq& |g_{n-1}-g_{n}\alpha|+|g_{n}-g_{n+1}\alpha| \\
            &=& g_{n-1}-g_{n}\alpha+g_{n+1}\alpha-g_n \\
            &=& a_n\alpha -(g_n-g_{n-1}) \\
            &=& \lbrace a_n \alpha \rbrace \textrm{ by } (v)
\end{array}$$ 
This finishes the proof. 
