- #1

Keen94

- 41

- 1

## Homework Statement

Prove that ∑

^{n}

_{j=0}n C r = 2

^{n}

## Homework Equations

Def

^{n.}of a combination.

Def

^{n.}of mathematical induction.

## The Attempt at a Solution

The formula is true for n=1

2=∑

_{j=0}

^{1}n C r

= 1 C 0 +1 C 1

=1 + 1

= 2

Now assume that for some

*k*∈ℕ and 0≤ j ≤

*k*we have

2

^{k}= ∑

^{k}

_{j=0}

**(k C j)**

Then

(2)(2

^{k})=2

^{k+1}=

**(2)**∑

^{k}

_{j=0}

**(k C j)**

LHS= ∑

^{k}_{j=0}

**(k C j)**+ ∑

^{k}_{j=0}

**(k C j)**

LHS= ∑

^{k}_{j=0}

**(k C j)**+ ∑

^{k+1}_{j=0}

**(k C j-1)**

LHS= ∑

^{k}_{j=0}

**(k C j)**+ ∑

^{k}_{j=0}

**(k C j-1)**+

**(k+1 C k+1)**

LHS= ∑

^{k}_{j=0}

**[ (k C j) + (k Cj-1) ]**+

**(k+1 C k+1)**

LHS= ∑

^{k}_{j=0}

**(k+1 C j) +**

**(k+1 C k+1)**

LHS= ∑

^{k+1}_{j=0}

**(k+1 C j)**

Does everything check? In addition, how was this formula discovered? How do people even find these things? Thanks again for the help guys and gals.

Last edited: