Waste less time on Facebook — follow Brilliant.
×

Binomial

Note by Dhruv Jstar
5 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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. Tapas Mazumdar · 4 months, 3 weeks ago

Log in to reply

need help Dhruv Jstar · 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...