# Proof about combinations and subsets

Let $\Omega_n={1,2,....,n}$ and for $0 \leq k \leq n$ let $\Omega^{\{k\}}$ be the collection of k element subsets of $\Omega_n$

Define the number $S^{n}_{k}$ as cardinality of $\Omega^{\{k\}}_n$

Use induction on n to prove for all $n \in N$ and $k \in Z$ with $0 \leq k \leq n$ that $S^{n}_{k}={n\choose k}$ by induction on n: Prove directly for all n, $S^{n}_0={n \choose 0}=1$. Prove the inductive step using the identities $S^{n}_{k} + S^{n}_{k+1}= S^{n+1}_{k+1}$ and ${n \choose k} + {n \choose k+1}={n+1 \choose k+1}$

I am ok withthe base case but I am having troubles proving the inductive hypothesis

Approach Assume for a $n \in N$ and $k \in Z$ with $0 \leq k \leq n$ $S^{n}_{k}= {n \choose k}$

Need to show $S^{n+1}_k={n+1 \choose k}$

$S^{n+1}_k = S^{n}_{k}+S^{n}_{k-1}$

I don't know how to tackle the $S^{n}_{k-1}$

• What is your definition of $\binom nk$?
– bof
Jun 2 '16 at 4:54
• the algebaric or combinatorial definition? Jun 2 '16 at 4:56

Hint: Now you have $1,2,\dots,n+1$, first consider how many sets in $\Omega^{\{k\}}_{n+1}$ do not contain the element $n+1$, and then count how many sets in $\Omega^{\{k\}}_{n+1}$ contain the element $n+1$.
• your claim proves the following $S^{n+1}_{k}=S^n_{k}+S^{n}_{k−1}$ Jun 2 '16 at 6:25
• what do you mean by don't know how to tackle $S^n_{k-1}$? Jun 2 '16 at 6:45
• you have $S^n_k = {n \choose k}$ for all $0\le k \le n$ and the identity ${n \choose k-1} + {n \choose k}={n+1 \choose k}$ Jun 2 '16 at 6:56