# Math Help - Bijective Proof

1. ## Bijective Proof

Don't know if this is in the right section but....

I need to write up a bijective proof of this:

$n+1 \choose{k+1}$ $= \sum_{m=k}^{n}$ $m \choose{k}$

I don't understand how that equals. I need to write up a little story to explain it like... if you're planning a party for n people but you want to make sure you don't miss anyone, so you add +1 persons to it and you need to order k amount of pizza, but don't want to not have too little pizza so you add +1 pizzas which would be the same as.... the other side of the equation.

Nicole

2. The bijective thing has kinda thrown me off but here's how it's proved...
(Although I suppose equality is a bijection so... I dunno)

Use induction.

Base case. $m=k$

${k \choose{k}} = {{k+1} \choose{k+1}}$ holds as both equal 1 so we have our inductive case.

Assume that it is true for $n$ (>k), i.e, assume that.

$\sum_{m=k}^n {m \choose{k}} = {n+1 \choose{k+1}}$

Now prove for the case n+1, i.e. show that...

$\sum_{m=k}^{n+1} {m \choose{k}} = {(n+1)+1 \choose{k+1}} = {n+2 \choose{k+1}}$

Now we have,

$\sum_{m=k}^{n+1} {m \choose{k}} = \sum_{m=k}^n {m \choose{k}} + {{n+1} \choose{k}} = {n+1 \choose{k+1}} + {{n+1} \choose{k}}$

Now just expand using ${n \choose k} = \frac{n!}{k!\,(n-k)!}$ and it should come out to be ${n+2 \choose{k+1}}$. Hence the relationship holds for all $n \geq k$.

(If you get stuck on the last part, look up Pascal's Rule).

3. well, a bijective proof is pretty much a proof that you give through just words. My professor wanted us to do that, only instead of just explaining it, kind of put a story to it...

4. Here is a hint,

if you want to do a bijection proof I recommend finding a sets $A$ and $X_k,X_{k+1},..,.X_n$ such that $X_i \cap X_j = \emptyset$ whenever $i \neq j$ and $A = \bigcup_{i} X_i$ with $|X_i | = \binom{i}{k}$ and $|A|=\binom{n+1}{k+1}$, i.e. use a counting argument, your set $A$ should be the number of ways to do something and your sets $X_i$ should be different disjoint cases you can break the counting process into. Once you have these sets the bijection you want can be taken from your counting argument in a straightforward fashion.

5. ok let me give you a stronger hint.

Lets start off by proving the identity

$

\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}

$

To do this consider how to breakdown counting the left hand side into two disjoint sets that correspond on the right hand side:

$

\underbrace{ \overbrace{ \Box \Box \ldots \Box \Box } ^k }_n

$

the boxes represent each of the n items and each box can have value 0 or 1 depending on if the item is chosen or not, and we must have that exactly k of the boxes are 1's and n-k are 0's.

$

\begin{matrix}
\underbrace{ \overbrace{ \Box \Box \ldots \Box \Box } ^k }_n
\end{matrix}
=
\begin{matrix}
1\underbrace{ \overbrace{\Box \Box \ldots \Box \Box } ^{k-1} }_{n-1} +
0\underbrace{ \overbrace{\Box \Box \ldots \Box \Box } ^{k} }_{n-1}
\end{matrix}
$

where I hope you can see why in the first term on the RHS we must choose k-1 1's and the second term we must choose k (this is because the first one is set to 1 in the first and 0 on the second.)

So this is the counting argument.

It should be clear and trivial how to construct the bijection from this counting argument, and your prof/teacher shouldn't force you to do it, this argument should suffice. If you really had to construct the bijection, then you would need to define the sets that the map acts on, which would be easiest by defining binary sequences of 0's and 1's of length n, n-1 with k,k-1 one's as appropriate. The map then you construct would come directly from the counting arguement and would be clearly a bijection by the same argument.

So for your case I hope you can see that this is just a repeated application on this simple counting argument.