Prove an inequality in proof of Poincaré recurrence theorem. I read this lecture made by Terence Tao.
(https://terrytao.wordpress.com/2008/01/30/254a-lecture-8-the-mean-ergodic-theorem/)
I tried to understand the proof of Poincaré recurrence theorem.
Everything is clear for me except one inequality:

Prove that $$\sum_{n=1}^{N}\sum_{m=1}^{N}\mu(E\cap T^{m-n}E) \le (\limsup_{n\to \infty}\mu(E\cap T^n(E))+o(1))N^2  $$

Here $\mu(E\cap T^{m-n}E)$ was originally replaced by $\mu(T^nE\cap T^mE)$ but it is written that this is the same and i agree with it.
I can also see that left-hand side is a sum of the measures $\mu(E\cap T^k(E))$, where $k=0,1,..N-1$
But I am able only to prove a different statement:
$$\sum_{n=1}^{N}\sum_{m=1}^{N}\mu(E\cap T^{m-n}E) \le (\sup_{n\le N}\mu(E\cap T^nE))N^2$$
According to this lecture, I have also one question:

How  theorem 1 in this lecture is connected with the original Poincaré recurrence theorem?(the theorem where one can find at Wikipedia page or somewhere else).

Regards
 A: First as you said one can simplifye the sums as follow $\sum_{m=1}^N \sum_{n=1}^N \mu(E \cap T^{m-n} E)= \sum_{k=N-1}^{N-1} (N -|k|) \mu(E \cap T^k E)$
Then because of the invariance of the measure $\mu(E \cap T^k E) = \mu(E \cap T^{-k} E)$
So $\sum_{k=N-1}^{N-1} (N -|k|) \mu(E \cap T^k E) = 2 \sum_{k=1}^{N-1} (N -k) \mu(E \cap T^k E) + N \mu(E)$
Our first upper bound : $ 2 \sum_{k=1}^{N-1} (N -|k|) \mu(E \cap T^k E) \leq 2 N \sum_{k=1}^{N-1} \mu(E \cap T^k E)$
Now we will justify the following lemma :

Let $x_n$ be a sequence of real beetween $0$ and $1$, we will note $x_+ = \lim \sup x_n$ then $\sum_{k=1}^{N} x_n \leq N x_+ +o(N)$

We have $\sum_{k=1}^N x_k = \sum_{k=1}^{\lfloor \sqrt{N} \rfloor} x_k + \sum_{k=\lfloor \sqrt{N} \rfloor+1}^N x_k \leq \lfloor \sqrt{N} \rfloor \max_{1 \leq k \leq \lfloor \sqrt{N} \rfloor} x_k + (N-\lfloor \sqrt{N} \rfloor -1)  \max_{ \lfloor \sqrt{N} +1 \rfloor \leq k \leq N} x_k$
Of course $\max_{ \lfloor \sqrt{N} +1 \rfloor \leq k \leq N} x_k = x_+ + o(1)$,
and because of the hypothesis $\max_{1 \leq k \leq \lfloor \sqrt{N} \rfloor} x_k \leq 1$
so $\sum_{k=1}^N x_k \leq \lfloor \sqrt{N} \rfloor + (N-\lfloor \sqrt{N} \rfloor -1)(x_+ +o(1)) = N x_+ + o(N) $
Applying this lemma we get $\sum_{k=1}^{N-1} \mu(E \cap T^k E) \leq N(\lim \sup \mu(E \cap T^k E) +o(1))$
and $\sum_{m=1}^N \sum_{n=1}^N \mu(E \cap T^{m-n} E) \leq 2 N^2 (\lim \sup \mu(E \cap T^k E) +o(1)) + N \mu(E)$
as $N \mu(E)=o(N^2)$ we have nearly our result.
I really don't know why I got a factor $2$..., if someone can check my proof.

To answer your second question

How theorem 1 in this lecture is connected with the original Poincaré recurrence theorem?(the theorem where one can find at Wikipedia page or somewhere else).

Tao use this equation to show that $\lim \sup \mu(E \cap T^n E) \geq \mu(E)^2$ that is given any set, after a long time, you are sure that the image of $E$ will eventually intersept $E$ enough to have measure $\mu(E)^2$.
