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}$

  • $\begingroup$ What is your definition of $\binom nk$? $\endgroup$
    – bof
    Jun 2 '16 at 4:54
  • $\begingroup$ the algebaric or combinatorial definition? $\endgroup$ 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$.

  • $\begingroup$ I know how to prove what you are stating but I don't know how it relates to the problem. Do you know how do it by induction? $\endgroup$ Jun 2 '16 at 6:15
  • $\begingroup$ that's exactly doing it by induction, since both counting relies on your hypothesis $\endgroup$
    – mastrok
    Jun 2 '16 at 6:17
  • $\begingroup$ your claim proves the following $S^{n+1}_{k}=S^n_{k}+S^{n}_{k−1}$ $\endgroup$ Jun 2 '16 at 6:25
  • $\begingroup$ what do you mean by don't know how to tackle $S^n_{k-1}$? $\endgroup$
    – mastrok
    Jun 2 '16 at 6:45
  • 1
    $\begingroup$ 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}$ $\endgroup$
    – mastrok
    Jun 2 '16 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.