# Binomial

Note by Dhruv Jstar
1 year, 3 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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

- 1 year, 2 months ago

Log in to reply

need help

- 1 year, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...