## Excel in math and science

### Master concepts by solving fun, challenging problems.

## It's hard to learn from lectures and videos

### Learn more effectively through short, conceptual quizzes.

## Our wiki is made for math and science

###
Master advanced concepts through explanations,

examples, and problems from the community.

## Used and loved by 4 million people

###
Learn from a vibrant community of students and enthusiasts,

including olympiad champions, researchers, and professionals.

## Comments

Sort by:

TopNewestI 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.

Log in to reply

need help

Log in to reply