The empty set matches the criteria, so

So

So

So

So

So we want to find a recurrence relation for . We can observe that given ,

Where is the number of valid subsets that do not contain .

But it is easily seen that , and so we get:

, as expected.