# How find this sum $\sum_{k=0}^{\left[\frac{n}{2}\right]}\frac{(-1)^k\binom{n-k}{k}}{n-k}$

How find this sum $$\sum_{k=0}^{\left[\dfrac{n}{2}\right]}\dfrac{(-1)^k\binom{n-k}{k}}{n-k}$$

My try:since $$\dfrac{(-1)^k}{n-k}=\int_{-1}^{0}x^{n-k-1}dx$$ then I can't

Thank you very much!

Following the well-known technique by Wilf we introduce the ordinary generating function $f(z) = \sum_{n\ge 1} f_n z^n$ where $f_n$ is our sum so that $$f(z) = \sum_{n\ge 1} z^n \sum_{k\ge 0} (-1)^k {n-k \choose k} \frac{1}{n-k}$$ and re-arrange terms to get $$f(z) = \log\frac{1}{1-z} + \sum_{k\ge 1} (-1)^k \sum_{n\ge 2k} {n-k\choose k} \frac{z^n}{n-k}$$ which is $$f(z) = \log\frac{1}{1-z} + \sum_{k\ge 1} (-1)^k \sum_{m\ge 0} {m+k\choose k} \frac{z^{2k+m}}{m+k} \\= \log\frac{1}{1-z} + \sum_{k\ge 1} (-1)^k z^{2k} \sum_{m\ge 0} \frac{m+k}{k} {m+k-1\choose k-1} \frac{z^m}{m+k} \\= \log\frac{1}{1-z} + \sum_{k\ge 1} (-1)^k \frac{z^{2k}}{k} \sum_{m\ge 0} {m+k-1\choose k-1} z^m \\ = \log\frac{1}{1-z} + \sum_{k\ge 1} (-1)^k \frac{z^{2k}}{k} \frac{1}{(1-z)^k}$$ which finally becomes $$\log\frac{1}{1-z} + \log \frac{1}{1+z^2/(1-z)} = \log\frac{1}{1-z} + \log \frac{1-z}{1-z+z^2} = \log \frac{1}{1-z+z^2}.$$ Now the roots of the denominator of the fractional term are $$\rho_{1,2} = \frac{1}{2} \pm \frac{\sqrt{3}i}{2}$$ and in particular we observe that $$1-z+z^2 = (1-z/\rho_1)(1-z/\rho_2)$$ (which is not true for the general quadratic), so we have $$f(z) = - \log(1-z/\rho_1) - \log(1-z/\rho_2) = \log\frac{1}{1-z/\rho_1} + \log\frac{1}{1-z/\rho_2}.$$
Extracting coefficients from this formula we obtain the following exact expression for $f_n:$ $$f_n = \frac{\rho_1^{-n}}{n} + \frac{\rho_2^{-n}}{n} = \frac{\rho_1^n}{n} + \frac{\rho_2^n}{n}$$ because $\rho_1\rho_2 = 1.$ Here we have made repeated use of the following expansion which is popular in combinatorics because it is the generating function of the species of cycles: $$\log\frac{1}{1-z} = \sum_{q\ge 1} \frac{z^q}{q}.$$
• In particular, since the $\rho_i$ are $6$th roots of unity, $nf_n$ is periodic with period $6$. Apr 12, 2014 at 20:40