Hi all.

I'm struggling with the one quite hard question for me:

Let I_n = {1,2,3,...,n} for n belong to N. A valid subset of I_n does not contain two numbers of the form x, x+1 for 1<=x<n. For example, {1,3,5} is valid but {1,3,4} is invalid. Let a_n denote the number of valid subsets of I_n.

How can i list explicitly the valid subsets of I_k for k<=4 ?

and how can i derive a recurrence relation for a_n (how can i obtain the formula)?

For any advice I'll be very appreciate

Regards