Evaluating $\sum_{k>\frac{N}{2}}\frac {1}{N}\cdot \frac{N-k}{k}$ Assuming $N$ is even, how can I evaluate the following sum:
$$\sum_{k>\frac{N}{2}}\frac{\binom{N}{k}(k-1)!(N-k)!}{N!}\cdot\frac{N-k}{N}=
\sum_{k>\frac{N}{2}}\frac {1}{N}\cdot \frac{N-k}{k}$$
I really don't know how to do it...
Thanks!
(Not HW BTW)
 A: First thing I would do is set $N=2M$. As observed by i707107, the lhs is $0$ for $k>N$, so your summation is finite and splits as follows
$$
S_N=\sum_{k=M+1}^{2M}\frac{1}{2M}\cdot\frac{2M-k}{k}=\sum_{k=M+1}^{2M}\frac{1}{k}-\frac{1}{2M}\sum_{k=M+1}^{2M}1
$$
$$
=\sum_{k=1}^{2M}\frac{1}{k}-\sum_{k=1}^{M}\frac{1}{k}-\frac{1}{2M}\cdot M
=H_{2M}-H_M-\frac{1}{2}
$$
$$
=H_N-H_{N/2}-\frac{1}{2}
$$
where $H_N$ denotes the $N$th harmonic number. You can get asymptotics for the latter if you wish: $H_N=\log N+\gamma+o(1)$ where $\gamma\simeq 0.577\ldots$ is Euler-Mascheroni constant. It follows that
$$
S_N=\log N+\gamma -(\log(N/2)+\gamma)-\frac{1}{2}+o(1)=\log 2-\frac{1}{2}+o(1)
$$
$$
\longrightarrow\log 2-\frac{1}{2}\simeq 0.193147\ldots
$$
If you simply want to bound it from below as you say, you can use integral comparison
$$
S_N=-\frac{1}{2}+\sum_{k=M+1}^{2M}\frac{1}{k}\geq-\frac{1}{2}+\int_{M+1}^{2M+1}\frac{1}{t}dt=-\frac{1}{2}+\log\left(\frac{2M+1}{M+1}\right).
$$
Note: with the above integral comparison, completing the upper bound, you recover that the limit is $\log 2-\frac{1}{2}$ without knowing anything about Euler-Mascheroni constant.
