Logo
Published on

Binomial coefficients and partial sums

Authors
  • avatar
    Name
    Vu Hung
    Twitter

Problem Statement

Let

Sn=∑k=0n(nk)S_n=\sum_{k=0}^n \binom{n}{k}

be the sum of the binomial coefficients for a fixed integer n≥1n\ge1.

  • Use the binomial theorem expansion of (1+x)n(1+x)^n to prove that Sn=2nS_n=2^n.
  • Use Pascal's identity
(nk)=(n−1k)+(n−1k−1)\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}

to prove the recurrence relation Sn=2Sn−1S_n=2S_{n-1}.

  • Evaluate the alternating partial sum
An=∑k=0n(−1)k(nk)A_n=\sum_{k=0}^n (-1)^k\binom{n}{k}

and explain why the sum of even-indexed coefficients equals the sum of odd-indexed coefficients.

  • By differentiating the expansion of (1+x)n(1+x)^n with respect to xx, show that
∑k=1nk(nk)=n2n−1.\sum_{k=1}^n k\binom{n}{k}=n2^{n-1}.

Hints

  • For (i): Substitute x=1x=1 into the binomial theorem.
  • For (ii): Sum Pascal's identity over the appropriate range of kk.
  • For (iii): Substitute x=−1x=-1 into the binomial theorem.
  • For (iv): Differentiate first, then substitute x=1x=1.

Solutions

(i) By the binomial theorem,

(1+x)n=∑k=0n(nk)xk.(1+x)^n=\sum_{k=0}^n \binom{n}{k}x^k.

Putting x=1x=1 gives

2n=∑k=0n(nk)=Sn.2^n=\sum_{k=0}^n \binom{n}{k}=S_n.

(ii) Using Pascal's identity,

Sn=∑k=0n(nk)=∑k=0n(n−1k)+∑k=0n(n−1k−1).\begin{aligned} S_n &=\sum_{k=0}^n\binom{n}{k}\\ &=\sum_{k=0}^n\binom{n-1}{k}+\sum_{k=0}^n\binom{n-1}{k-1}. \end{aligned}

The out-of-range terms are zero, so each sum equals Sn−1S_{n-1}. Hence

Sn=2Sn−1.S_n=2S_{n-1}.

(iii) By the binomial theorem again,

An=∑k=0n(−1)k(nk)=(1−1)n=0.A_n=\sum_{k=0}^n(-1)^k\binom{n}{k}=(1-1)^n=0.

Therefore

∑0≤k≤nk even(nk)−∑0≤k≤nk odd(nk)=0,\sum_{\substack{0\le k\le n\\ k\text{ even}}}\binom{n}{k} - \sum_{\substack{0\le k\le n\\ k\text{ odd}}}\binom{n}{k} =0,

so the even-indexed and odd-indexed sums are equal.

(iv) Differentiate

(1+x)n=∑k=0n(nk)xk(1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k

to get

n(1+x)n−1=∑k=1nk(nk)xk−1.n(1+x)^{n-1}=\sum_{k=1}^n k\binom{n}{k}x^{k-1}.

Putting x=1x=1 gives

∑k=1nk(nk)=n2n−1.\sum_{k=1}^n k\binom{n}{k}=n2^{n-1}.

Takeaways

  • Substituting special values into the binomial theorem turns an expansion into a sum identity.
  • Pascal's identity explains why the total sum of coefficients doubles from one row to the next.
  • Differentiating a generating expansion is a powerful way to evaluate weighted sums.

Further Readings

Connect with me