How many combinations can be formed from 5 binary digits?

[otto]

So look at what I've done:
<br /> {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)!}<br /><br /> =<br /> \frac {(n+1)}{k} \cdot<br /> <br /> \frac { n!}{(n-(k-1))!\cdot (k-1)!} =<br /> <br /> \frac {(n+1)}{k} <br /> <br /> \cdot {n \choose k-1}<br /> <br />
oops I accidentally posted this before I finished my calculations, please ignore this until I've finished it. Thanks

[edit] So Yea, that's 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. I am trying to figure out the proof for: \sum\limits_{i=1}^n {n \choose k} = 2^n<br />

 

[jedishrfu]

Perhaps you can get some inspiration from Pascal's triangle

http://en.m.wikipedia.org/wiki/Pascal_triangle

 

[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: <br /> <br /> \sum_{k=0}^n{n+1 \choose k} =<br /> <br /> \sum_{k=0}^n {n \choose k} +{n \choose k-1} <br /> <br /> I have the problem that k-1 will equal -1 in the first iteration of the summation. don't know how to fix this.

 

[Mentallic]

I am trying to figure out the proof for: <br /> <br /> <br /> \sum\limits_{i=1}^n {n \choose k} = 2^n<br />

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
<br /> \sum\limits_{k=0}^n {n \choose k} = 2^n<br />

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}

 

[Whovian]

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: <br /> <br /> \sum_{k=0}^n{n+1 \choose k} =<br /> <br /> \sum_{k=0}^n {n \choose k} +{n \choose k-1}<br /> <br /> I have the problem that k-1 will equal -1 in the first iteration of the summation. don't know how to fix this.

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.

 

[FactChecker]

You are right that the proof by induction approach can turn into a can of worms.
Notice that <br /> \sum\limits_{k=0}^n {n \choose k}<br /> 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?