Sum of $\{n\sqrt{2}\}$ I would like to prove (rigorously, not intuitively) that
$$\sum_{n=1}^N \{n\sqrt{2}\}=\frac{N}{2}+\mathcal{O}(\sqrt{N})$$
where $\{\}$ is the "fractional part" function. I understand intuitively why this is true, and that's how I came up with this claim - $\{n\sqrt{2}\}$ behaves like a random variable uniformly distributed in $(0,1)$, and treating it as a random variable makes the sum analogous to a random walk, and the $\mathcal{O}(\sqrt{N})$ bound can be shown using expected values. 
However, just saying that $\{n\sqrt{2}\}$ behaves "like a random variable" is highly non-rigorous. Can someone show me how to justify this in a more airtight way (ideally without using any theorems that require specialized background knowledge)?
Thanks!
 A: Writing
\begin{align}
&\quad \sum_{n=1}^N \left( n\sqrt{2} - \lfloor n\sqrt{2} \rfloor \right) \\
&=\int_1^N \left( n\sqrt{2} - \lfloor n\sqrt{2} \rfloor \right) {\rm d}n + {\cal O}(1) \tag{1} \\
&=\frac{1}{\sqrt{2}} \int_\sqrt{2}^{\sqrt{2}N} \left(x- \lfloor x \rfloor \right) {\rm d}x + {\cal O}(1)  \\
&=\frac{1}{\sqrt{2}} \Bigg( N^2 - 1 - \Bigg[ \frac{\sqrt{2}N \left(\sqrt{2}N-1\right)}{2} + \frac{\left\{\sqrt{2}N\right\} \left(1-\left\{\sqrt{2}N\right\}\right)}{2} \\
&\quad - \frac{\sqrt{2} \left(\sqrt{2}-1\right)}{2} - \frac{\left\{\sqrt{2}\right\} \left(1-\left\{\sqrt{2}\right\}\right)}{2} \Bigg] \Bigg) + {\cal O}(1) \\
&=\frac{N}{2} + {\cal O}(1)
\end{align}
where we used
$$
\int_0^x \lfloor t \rfloor \, {\rm d}t = \frac{x(x-1)}{2} + \frac{\left\{x\right\}\left(1-\left\{x\right\}\right)}{2} \, .
$$
The order follows from the fact that
$$
\frac{\left( \sqrt{2}N - \lfloor \sqrt{2}N \rfloor \right) + \left( \sqrt{2} - \lfloor \sqrt{2} \rfloor \right)}{2} = {\cal O}(1) \tag{2}
$$
and
$$\int_1^{N} \left( n\sqrt{2} - \lfloor n\sqrt{2} \rfloor \right)'' {\rm d}n \tag{3} \\
= \left( \sqrt{2}n - \lfloor \sqrt{2}n \rfloor \right)'\big|_{n=N} - \left( \sqrt{2}n - \lfloor \sqrt{2}n \rfloor \right)'\big|_{n=1} \\
=\sqrt{2} \sum_{k=-\infty}^{\infty}\left[ \delta\left( \sqrt{2} - k   \right) - \delta\left( \sqrt{2}N - k  \right) \right]
$$
but this requires Euler-Maclaurin.

Due to the harsh critic about my somewhat heuristic argument I want to correct my approach as far as possible.
Set $$f(x)=x-\lfloor x \rfloor$$ and $$f_n(x)=\frac{1}{2} - \frac{1}{\pi} \sum_{k=1}^n \frac{\sin(2\pi k x)}{k} \, ,$$such that
$$
\lim_{n\rightarrow \infty} f_n(x) = f(x) \, .
$$
Since $f_n$ is differentiable we can use Euler-Maclaurin to calculate the sum
$$
\sum_{k=1}^N f_n(ak)
$$
with some $a$. The integral in (1) does not create much of an issue in the limit $n \rightarrow \infty$, since the limit is piecewise continuous and the integral can be splitted accordingly and then integrated. Also the limit of (2) is of ${\cal O}(1)$. So the problematic term which needs to be examined is the remainder $R_2$ ((3) was very heuristic) which can be written as
$$
R_2=\int_1^N B_2\left(t-\lfloor t \rfloor\right) \frac{\rm d}{{\rm d}t} f_n'(at) \, {\rm d}t
$$
neglecting unnecessary constants and $B_2$ is the second Bernoulli polynomial. We can express
\begin{align}
f_n'(at) &= 1-\sum_{k=-n}^{n} {\rm e}^{i2\pi k at} = 1 - \frac{\sin\left((2n+1)\pi at\right)}{\sin\left(\pi at\right)} \\
B_2\left(t-\lfloor t \rfloor\right) &= \left(t-\lfloor t \rfloor\right)(\left(t-\lfloor t \rfloor - 1\right) + \frac{1}{6} = \lim_{M \rightarrow \infty} \sum_{k=1}^M \frac{\cos(2\pi kt)}{\pi^2 k^2}
\end{align}
and integrate by parts
$$
R_2=-B_2\left(t-\lfloor t \rfloor\right) \frac{\sin\left((2n+1)\pi at\right)}{\sin\left(\pi at\right)} \Bigg|_{1}^{N} - 2 \sum_{k=1}^{M} \int_1^N   \frac{\sin(2\pi kt)}{\pi k}  \frac{\sin\left((2n+1)\pi at\right)}{\sin\left(\pi at\right)} \, {\rm d}t \tag{4} \, .
$$
For $a$ not an integer, the first term is bounded and ${\cal O}(1)$ as $n \rightarrow \infty$. The integral can be viewed as a functional for $n \rightarrow \infty$ in which case the Dirichlet kernel acts as a periodic delta-distribution $\sum_{m=-\infty}^{\infty} \delta(at-m)$
$$
\lim_{n \rightarrow \infty} \int_1^N   \frac{\sin(2\pi kt)}{\pi k}  \frac{\sin\left((2n+1)\pi at\right)}{\sin\left(\pi at\right)} \, {\rm d}t = \sum_{m=\lceil a \rceil}^{\lfloor Na \rfloor} \frac{\sin\left(\frac{2\pi km}{a}\right)}{\pi k a} \, .
$$
Evaluating
$$
\sum_{m=\lceil a \rceil}^{\lfloor Na \rfloor} \lim_{M\rightarrow\infty} -2\sum_{k=1}^{M} \frac{\sin\left(\frac{2\pi km}{a}\right)}{\pi k a} = \sum_{m=\lceil a \rceil}^{\lfloor Na \rfloor} \frac{2\{m/a\}-1}{a} \tag{5}
$$
and using $\sum_{n=1}^{N}\{an\} = \frac{N}{2} + {\cal O}(?)$
this becomes ${\cal o}(N)$. So it is actually true ${\cal O}(1)$ does not follow.

We continue with the integral in (4) for $N$ integer
\begin{align}
&\quad -2\sum_{k=1}^\infty \int_1^N   \frac{\sin(2\pi kt)}{\pi k}  \frac{\sin\left((2n+1)\pi at\right)}{\sin\left(\pi at\right)} \, {\rm d}t \\
&=-4\sum_{m=1}^n \sum_{k=1}^\infty \int_1^N \frac{\sin(2\pi kt)\cos(2\pi m a t)}{\pi k} \, {\rm d}t \\
&=\frac{4}{\pi^2} \sum_{m=1}^n \sum_{k=1}^\infty \frac{\cos^2(N\pi m a)-\cos^2(\pi ma)}{k^2-m^2 a^2} \\
&=2\sum_{m=1}^n \left[ \frac{\cos^2(N\pi m a)-\cos^2(\pi ma)}{\pi^2 m^2 a^2} - \frac{\cot(\pi ma)\left(\cos^2(N\pi ma) - \cos^2(\pi ma)\right)}{\pi ma} \right]
\end{align}
where $a$ must be an irrational number now. The first term is ${\cal O}(1)$ for $n\rightarrow \infty$.
Any idea for the second? 
It can be rewritten as
\begin{align}
&\quad \, \, \sum_{m=1}^n \frac{\cot(\pi ma)\left(\cos^2(N\pi m a) - \cos^2(\pi ma)\right)}{\pi ma} \\
&= \sum_{m=1}^n \frac{\cot(\pi ma)\left(\cos(N2\pi ma) - \cos(2\pi ma)\right)}{2\pi ma} \\
&= - \sum_{m=1}^{n}\cos(m\pi a) \, \frac{\sin\left((N+1)m\pi a\right)}{m\pi a} \, \frac{\sin\left((N-1)m\pi a\right)}{\sin(m\pi a)} \\
&= - \sum_{m=1}^{n} \frac{\sin\left((N+2)m\pi a\right)}{m\pi a} \, \frac{\sin\left((N-1)m\pi a\right)}{\sin(m\pi a)} + \sum_{m=1}^n \frac{ \sin\left(N2\pi ma\right) - \sin\left(2\pi ma\right) }{2\pi ma}
\end{align}
so the second sum is bounded again $\forall N$ and $n \rightarrow \infty$.
Not sure if it helps, but I have the following two identities for the sines
$$
\frac{\sin\left((N-1)nx\right)}{\sin(nx)} = \sum_{l=2}^N \cos\left((N-l)nx\right) \cos^{l-2}(nx) 
$$
and
$$
\frac{\sin\left((N-1)nx\right)}{\sin(nx)} = 1+2\sum_{l=1}^{\frac{N}{2}-1} \cos\left(l2nx\right) \, ,
$$
but evaluating this feels as if I'm running in circles.
I added a Figure of the RHS of (5) up to $N=10^6$ which doesn't look anything like $\log$, so either the numbers are just too small or I dont why it has to be $\log$.

A: This is along the same line as another problem and my answer there: Determine whether $\sum_{n=1}^\infty \frac {(-1)^n|\sin(n)|}{n}$ converges
We need Koksma's inequality p. 143, Theorem 5.1 of 'Uniform Distribution of Sequences' by Kuipers and Niederreiter.

Theorem [Koksma]
Let $f$ be a function on $I=[0,1]$ of bounded variation $V(f)$, and suppose we are given $N$ points $x_1, \ldots , x_N$ in $I$ with discrepancy
$$
D_N:=\sup_{0\leq a\leq b\leq 1} \left|\frac1N \#\{1\leq n\leq N: x_n  \in (a,b) \} -(b-a)\right|.
$$
Then
$$
\left|\frac1N \sum_{n\leq N} f(x_n) - \int_I f(x)dx \right|\leq V(f)D_N.
$$

To control the discrepancy, We apply the following theorem, for the sequence $x_n = n\alpha - \lfloor n \alpha \rfloor$. Note that with $\alpha = \sqrt 2$, it has a bounded partial quotients in its continued fraction.
Theorem 3.4 of p125 in the Kuipers and Niederreiter's book, states that

If an irrational real $\alpha$ has a bounded partial quotients, then the discrepancy $D_N$ satisfies
$$
N D_N\ll \log N.
$$

Then applying these to your problem with $f(x)=x$, we obtain
$$
\bigg\vert\frac1N \sum_{n\leq N} \{ n\sqrt 2\} - \int_0^1 x \ dx\bigg\vert \ll \frac{\log N}N.
$$
Therefore, we have an estimate of
$$
\sum_{n\leq N} \{n\sqrt 2\}=\frac N2 + O(\log N).
$$

To obtain a more precise estimate, we have $V(f)=1$ for $f(x)=x$. Also, Theorem 3.4 describes how $O(\log N)$ term behaves in a more precise way. Using those, we have
$$
\Bigg\vert \sum_{n\leq N} \{n\sqrt 2\}-\frac N2 \Bigg\vert \leq  3+\left(\frac1{\log \xi}+\frac{2}{\log 3}\right)\log N.
$$
Here we use $\xi=\frac{1+\sqrt 5}2$ and the continued fraction partial quotients are bounded by $2$ (It is in fact $[1;2,2,2,\ldots]$).
