×

# Binomial

Note by Dhruv Jstar
5 months ago

Sort by:

I here want to address Kartik Sharma for his truly marvelous approach and also to give him the credits for this approach. The solution you'll see below is an exact replication of his solution in one of his problems.

$$\displaystyle \text{Proposition #1:} \large \sum_{m=1}^n {\left(\sum_{k=1}^m{a_k}\right) \binom{n}{m} {(-1)}^{m-1}} = \sum_{m=0}^{n-1}{\binom{n-1}{m} a_{m+1}{(-1)}^m}$$

$$\text{Proof:}$$

LHS can be written as -

$$\displaystyle \binom{n}{1}a_1 - \binom{n}{2}(a_1 + a_2) + \binom{n}{3} a_3 - \cdots + {(-1)}^{n-1} \binom{n}{n} (a_1 + a_2 + \cdots + a_n)$$

$$\displaystyle = \left(\binom{n}{1} - \binom{n}{2} + \binom{n}{3} -\cdots +{(-1)}^{n-1}\binom{n}{n}\right) a_1 +\left(- \binom{n}{2} + \binom{n}{3} -\cdots +{(-1)}^{n-1}\binom{n}{n}\right) a_2 + \cdots \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \displaystyle + \left( {(-1)}^{n-1} \binom{n}{n}\right) a_n$$

Using the fact that LaTeX: $$-\binom{n}{0} +\binom{n}{1} - \binom{n}{2} + \binom{n}{3} -\cdots +{(-1)}^{n-1}\binom{n}{n} = 0$$,

$$\displaystyle = \binom{n}{0} a_1 + \left(\binom{n}{0} - \binom{n}{1}\right) a_2 + \cdots + \left(\binom{n}{0} -\binom{n}{1} + \binom{n}{2} - \binom{n}{3} +\cdots +{(-1)}^{n-1}\binom{n}{n-1}\right) a_n$$

$$\displaystyle \text{Proposition #2 :} \sum_{r=0}^k {\binom{n}{r} {(-1)}^r} = \binom{n-1}{k} {(-1)}^k$$

$$\text{Proof:}$$

We use induction (since it is very easy to observe using Pascal's triangle addition law).

$$\displaystyle S(k=0) : \binom{n}{0} = \binom{n-1}{0}$$. LaTeX: $$\text{True}$$

$$\displaystyle S(k) : \sum_{r=0}^k {\binom{n}{r} {(-1)}^r} = \sum_{r=0}^{k-1} {\binom{n}{r} {(-1)}^r} + \binom{n}{k} {(-1)}^k$$

$$\displaystyle = \binom{n-1}{k-1} {(-1)}^{k-1} + \binom{n}{k} {(-1)}^k = \binom{n-1}{k} {(-1)}^k$$

$\displaystyle \mathbf{Q.E.D.}\blacksquare$

Coming back to our proof, we use this formula.

$\displaystyle = \binom{n-1}{0} a_1 - \binom{n-1}{1} a_2 + \cdots {-1}^{n-1} \binom{n-1}{n-1} a_n$

$\displaystyle = \sum_{m=0}^{n-1}{\binom{n-1}{m} a_{m+1} {(-1)}^m}$

$\displaystyle \mathbf{Q.E.D.}\blacksquare$

Now if we substitute $$a_k = \frac{1}{k}$$,

$$\displaystyle \sum_{m=1}^n {\binom{n}{m} H_m {(-1)}^{m-1}} = \sum_{m=0}^{n-1}{\binom{n-1}{m} \frac{{(-1)}^m}{m+1}} = \frac{1}{n}$$

Note that $$H_m$$ denotes the harmonic number which is given by

$H_m = \displaystyle \sum_{k=1}^m \dfrac 1m$

as stated in your problem. · 4 months, 3 weeks ago