Evaluate the sum $$\binom{2n}{n}+\binom{3n}{n}+\binom{4n}{n} + \cdots +\binom{kn}{n}$$

My Attempt:

Given sum = coefficient of $x^n$ in the expansion $$\{(1+x)^{n}+(1+x)^{2n}+(1+x)^{3n}+\cdots+(1+x)^{kn}\}-1 \\ = \text{coefficient of $x^n$ in}~~ \frac{(1+x)^n\{(1+x)^{nk}-1\}}{(1+x)^n-1}-1$$

But I am not able to go beyond this or there is some method using combinatorial argument

  • 2
    $\begingroup$ You can write the fraction as $\left(1+\frac1{(1+x)^n-1}\right)\left((1+x)^{nk}-1\right)$, and then use the fact that the coefficient of $x^n$ is the $n$th derivative of this expression, evaluated at $0$, divided by $n!$. This will be rather tedious to calculate but doable given enough patience. $\endgroup$
    – YiFan
    Mar 16 '20 at 3:22
  • $\begingroup$ Do you mean the first term to be ${n \choose n}$? You're using that in your attempt. $\endgroup$ Mar 16 '20 at 3:38
  • $\begingroup$ Yes. I did so that summation formula of Geometric Progression could be applied $\endgroup$
    – Maverick
    Mar 16 '20 at 3:44
  • 4
    $\begingroup$ Do you expect that there should be a closed form? On what basis? (It seems unlikely at first sight, and Wolfram|Alpha doesn't provide one.) $\endgroup$
    – joriki
    Mar 16 '20 at 4:36
  • 1
    $\begingroup$ @Robert Adding 1 shouldn't be that big of a deal... 😁 $\endgroup$
    – Wolfgang
    Mar 16 '20 at 10:28

The result I get is the following:

Applying the binomial expansion we have that $$(1+x)^{2n}=\sum\limits_{j=0}^{2n}\binom{2n}{j}x^j.$$ Since we want to keep track of the $n-$th coefficient, all we have to do is to derivate this function $n$ times, evaluate at $x=0$ and divide by $n!$: $$n!\binom{2n}{n}=\dfrac{d^{(n}}{dx}\left( (1+x)^{2n} \right)\big|_{x=0}\Longrightarrow \binom{2n}{n}=\dfrac{1}{n!}\dfrac{d^{(n}}{dx}\left( (1+x)^{2n} \right)\big|_{x=0}$$

Then, the sum we want to compute can be written as a sum of derivatives: $$\sum\limits_{j=2}^k\binom{jn}{n}=\sum\limits_{j=2}^k\dfrac{1}{n!}\dfrac{d^{(n}}{dx}\left( (1+x)^{jn} \right)\big|_{x=0}=\dfrac{1}{n!}\dfrac{d^{(n}}{dx}\left( \sum\limits_{j=2}^k(1+x)^{jn} \right){\huge|}_{x=0}.$$

This is the farthest I could reach when looking for a compact way of writing the initial sum. Anyways, the initial form looks way more compact and friendly. If you are looking for a method to approximate the result, applying the derivatives (numerically) could even be faster than computing the original sum. It may be worth trying.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.