Difficult induction proof

[Miniputtz]

Prove using induction that if \(\displaystyle n\,\, \in \,\, \mathbb{N} \,\, \cup\,\, \{0 \}\), \(\displaystyle j \,\, \in \,\, \mathbb{N}\,\, \cup \,\, \{0 \}\) with \(\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 \(\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

 

[mark07]

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 \(\displaystyle x\in X\). Then \(\displaystyle X = Y \cup \{ x \}\) where Y is \(\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.