Difficult induction proof

Miniputtz

New member
Joined
Feb 27, 2006
Messages
6
Prove using induction that if n    N    {0}\displaystyle n\,\, \in \,\, \mathbb{N} \,\, \cup\,\, \{0 \}, j    N    {0}\displaystyle j \,\, \in \,\, \mathbb{N}\,\, \cup \,\, \{0 \} with 0jn\displaystyle 0\le j \le n and X is a set with n elements,

Then the number of subsets of X which have j elements is (nj)\displaystyle n \choose j

I've been working on this problem and get stuck when I try the inductive step. I'm not quite sure on how to start the inductive step.
Thank you in advance
 
When j=0, result follows immediately. Let j>0 for the following arguments.

Induction step: Assume that the statement holds for sets with n elements. Let X be a set with n+1 elements. Let xX\displaystyle x\in X. Then X=Y{x}\displaystyle X = Y \cup \{ x \} where Y is X{x}\displaystyle X - \{ x \}.

Claim: Number of subsets of X with j elements is the number of subsets of Y with j elements plus the number of subsets of Y with j-1 elements (by including x to each). (You may need to prove this if it's not obvious to you.)

By the claim and the induction hypothesis, number of subsets of X with j elements is then

\(\displaystyle \L {n \choose j} + {n \choose {j-1}}\)

Show that this is equal to

\(\displaystyle \L {n+1} \choose j\)

which is not difficult at all.
 
Top