×

# Binomial

Note by Dhruv Jstar
10 months, 2 weeks 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}$$

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$

- 10 months ago

need help

- 10 months, 2 weeks ago