Prove that $$\binom{n}{1}(1-x)-\frac{1}{2}\binom{n}{2}(1-x)^2+\frac{1}{3}\binom{n}{3}(1-x)^3+\cdots \cdots +(-1)^{n-1}\frac{1}{n}(1-x)^n$$

$$=(1-x)+\frac{1}{2}(1-x^2)+\frac{1}{3}(1-x^3)+\cdots +\frac{1}{n}(1-x^n)$$

what i try

$$\bigg[1-(1-x)\bigg]^n=\binom{n}{0}-\binom{n}{1}(1-x)+\binom{n}{2}(1-x)^2-\cdots +(-1)^n\binom{n}{n}(1-x)^n$$

Integrate with respect to $x$

$$\frac{x^{n+1}}{n+1}-1=-\binom{n}{0}(1-x)+\binom{n}{1}\frac{(1-x)^2}{2}-\binom{n}{2}\frac{(1-x)^3}{3}+\cdots +(-1)^{n-1}\frac{(1-x)^{n+1}}{n+1}$$

How do I solve it? Help me, please!

  • 1
    $\begingroup$ Use a direct approach? $(1-x)^k=\sum_{j=0}^k \binom{k}{j}(-x)^j$. Do this for all the terms on the left side and collect all like powers of $x$. You should get right side. $\endgroup$ – herb steinberg Feb 18 at 4:10
  • $\begingroup$ did not ubderstand can you explain in detail way $\endgroup$ – jacky Feb 18 at 15:35
  • $\begingroup$ For example the coefficient of the term$(-x)^j$ is obtained by $T_j=\sum_{k=j}^n\frac{1}{k}\binom{n}{k}\sum_{k=1}^j\binom{k}{j}$, for $j\ne 0$,so we need to show $\sum_{k=1}^n(-1)^{k-1}\frac{1}{k}\binom{n}{k}+\sum_{j=1}^nT_j(-x)^j$ is identical to the right side. $\endgroup$ – herb steinberg Feb 19 at 1:30

We put

$$S_n(x) = \sum_{p=1}^n \frac{1}{p} {n\choose p} (-1)^{p+1} (1-x)^p.$$

Working first with the coefficient on $[x^q]$ where $1\le q\le n$ we see that it is

$$\sum_{p=q}^n (-1)^{p+1} \frac{1}{p} {n\choose p} {p\choose q} (-1)^q.$$


$${n\choose p} {p\choose q} = \frac{n!}{(n-p)! \times q! \times (p-q)!} = {n\choose q} {n-q\choose n-p}$$

so we find

$$ (-1)^q {n\choose q} \sum_{p=q}^n (-1)^{p+1} \frac{1}{p} {n-q\choose n-p} \\ = (-1)^q {n\choose q} \sum_{p=0}^{n-q} (-1)^{p+q+1} \frac{1}{p+q} {n-q\choose n-p-q} \\ = {n\choose q} \sum_{p=0}^{n-q} (-1)^{p+1} \frac{1}{p+q} {n-q\choose p}.$$


$$f(z) = \frac{(-1)^{n-q+1} (n-q)!}{z+q} \prod_{k=0}^{n-q} \frac{1}{z-k}$$

we have

$$\sum_{p=0}^{n-q} \mathrm{Res}_{z=p} f(z) = \sum_{p=0}^{n-q} \frac{(-1)^{n-q+1} (n-q)!}{p+q} \prod_{k=0}^{p-1} \frac{1}{p-k} \prod_{k=p+1}^{n-q} \frac{1}{p-k} \\ = \sum_{p=0}^{n-q} \frac{(-1)^{n-q+1} (n-q)!}{p+q} \frac{1}{p!} (-1)^{n-q-p} \frac{1}{(n-q-p)!} \\ = \sum_{p=0}^{n-q} (-1)^{p+1} \frac{1}{p+q} {n-q\choose p}.$$

This is the target sum omitting the binomial coefficient in front. Now the residue at infinity of $f(z)$ is clearly zero and hence the sum must be (residues sum to zero)

$$- \mathrm{Res}_{z=-q} f(z) = - (-1)^{n-q+1} (n-q)! \prod_{k=0}^{n-q} \frac{1}{-q-k} \\ = - (n-q)! \prod_{k=0}^{n-q} \frac{1}{q+k} = -(n-q)! \frac{(q-1)!}{n!}.$$

Restoring the binomial coefficient in front we thus have

$$[x^q] S_n(x) = -{n\choose q} (n-q)! \frac{(q-1)!}{n!}$$

or alternatively

$$\bbox[5px,border:2px solid #00A000]{ [x^q] S_n(x) = - \frac{1}{q},}$$

as claimed. Comntinuing with the constant coefficient we find

$$[x^0] S_n(x) = \sum_{p=1}^n \frac{1}{p} {n\choose p} (-1)^{p+1} [x^0] (1-x)^p = \sum_{p=1}^n \frac{1}{p} {n\choose p} (-1)^{p+1}.$$

Using the same technique as before we introduce

$$g(z) = \frac{(-1)^{n+1} n!}{z} \prod_{k=0}^{n} \frac{1}{z-k}$$

We get for

$$\sum_{p=1}^n \mathrm{Res}_{z=p} g(z) = \sum_{p=1}^n \frac{(-1)^{n+1} n!}{p} \prod_{k=0}^{p-1} \frac{1}{p-k} \prod_{k=p+1}^{n} \frac{1}{p-k} \\ = \sum_{p=1}^n \frac{(-1)^{n+1} n!}{p} \frac{1}{p!} (-1)^{n-p} \frac{1}{(n-p)!} \\ = \sum_{p=1}^n \frac{1}{p} {n\choose p} (-1)^{p+1}.$$

This is the target sum. Now the residue at infinity is zero so this sum must be equal to

$$- \mathrm{Res}_{z=0} g(z) = - \mathrm{Res}_{z=0} \frac{(-1)^{n+1} n!}{z^2} \prod_{k=1}^{n} \frac{1}{z-k} \\ = (-1)^{n} n! \left.\left( \prod_{k=1}^{n} \frac{1}{z-k}\right)'\right|_{z=0} \\ = (-1)^{n} n! \left.\left( \prod_{k=1}^{n} \frac{1}{z-k} \sum_{k=1}^n \frac{1}{k-z} \right)\right|_{z=0} = (-1)^n n! \times \frac{(-1)^n}{n!} \sum_{k=1}^n \frac{1}{k}.$$

We have shown that (with harmonic numbers)

$$\bbox[5px,border:2px solid #00A000]{ [x^0] S_n(x) = \sum_{k=1}^n \frac{1}{k} = H_n,}$$

which concludes the argument. If desired we may write this as

$$S_n(x) = \sum_{k=1}^n \frac{1}{k} - \sum_{q=1}^n \frac{1}{q} x^q$$


$$\bbox[5px,border:2px solid #00A000]{ S_n(x) = \sum_{q=1}^n \frac{1}{q} (1 - x^q).}$$


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.