Evaluating $\sum_{k>\frac{N}{2}}\frac {1}{N}\cdot \frac{N-k}{k}$

Question

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)

Answer 1

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.