# Gosh darn combinatorics

1. Sep 14, 2014

### otto

So look at what Ive done:
$${n+1 \choose k} = \frac {(n+1)!} {(n+1-k)! \cdot k!} = \frac {(n+1)\cdot n!}{(n-(k-1))!\cdot k \cdot (k-1)!}$$$$= \frac {(n+1)}{k} \cdot \frac { n!}{(n-(k-1))!\cdot (k-1)!} = \frac {(n+1)}{k} \cdot {n \choose k-1}$$

oops I accidentally posted this before I finished my calculations, please ignore this until I've finished it. Thanks

 So Yea, thats it. Thing is, somethings wrong (try plugging numbers into it). Anyways, I need to figure out what I did wrong. This is just part of a massive can of worms. Im trying to figure out the proof for: $$\sum\limits_{i=1}^n {n \choose k} = 2^n$$

Last edited: Sep 14, 2014
2. Sep 14, 2014

### Staff: Mentor

3. Sep 14, 2014

### otto

Pascals identity to be exact. I've read some "proofs" if you can call them that, but they were rather not helpful. math stack exchange.

When I replace my summation from k=0 to n, with the combinatorics: $\sum_{k=0}^n{n+1 \choose k} = \sum_{k=0}^n {n \choose k} +{n \choose k-1}$ I have the problem that k-1 will equal -1 in the first iteration of the summation. dont know how to fix this.

4. Sep 14, 2014

### Mentallic

The lower limit of the sum should be k=0 because i isn't present in the combinatoric and for reasons you'll eventually find out, it should start at 0.

So you want to prove
$$\sum\limits_{k=0}^n {n \choose k} = 2^n$$

then simply notice that the binomial expansion is

$$(a+b)^n = \sum\limits_{k=0}^n{n\choose k}a^{n-k}b^k$$

So for what values of a and b is

$$\sum\limits_{k=0}^n{n\choose k}a^{n-k}b^k\equiv \sum\limits_{k=0}^n {n \choose k}$$

5. Sep 21, 2014

### Whovian

The problem here is that $\binom{n+1}k=\binom nk+\binom n{k-1}$ only for k>0; if k=0 then it's just $\binom nk$, as both are 1. I think the convention is often to let $\binom n{-1}=0$; then $\binom{n+1}k=\binom nk+\binom n{k-1}$ even when k=0.

6. Sep 22, 2014

### FactChecker

You are right that the proof by induction approach can turn into a can of worms.
Notice that $\sum\limits_{k=0}^n {n \choose k}$ is the total number of ways that any number of items (including 0 and n) can be selected from n items.

If we indicate whether an item is selected or not by 1 or 0, respectively, and put the 1's and 0's in order, we can represent any set of selected items.

For instance, starting with n=5 items, 10110 = select first, don't select second, select third, select fourth, don't select fifth, represents one way of selecting 3 of the 5. Now, how many zero/one patterns can we get from 5 binary digits?