Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 1 down vote accepted

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}.$$

Two similar calculations can be found at this MSE link.

share|cite|improve this answer
In particular, since the $\rho_i$ are $6$th roots of unity, $nf_n$ is periodic with period $6$. – Greg Martin Apr 12 '14 at 20:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.