# Thread: The valid subsets and reccurence relation

1. ## The valid subsets and reccurence relation

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

2. $\displaystyle k=0:$
The empty set matches the criteria, so $\displaystyle I_0 = 1$

$\displaystyle k=1:$
$\displaystyle \phi , \left\{1\right\}$
So $\displaystyle I_1=2$

$\displaystyle k=2:$
$\displaystyle \phi , \left\{1\right\},\left\{2\right\}$
So $\displaystyle I_2=3$

$\displaystyle k=3:$
$\displaystyle \phi , \left\{1\right\},\left\{2\right\}, \left\{3\right\}, \left\{1,3\right\}$
So $\displaystyle I_3=5$

$\displaystyle k=4:$
$\displaystyle \phi , \left\{1\right\},\left\{2\right\}, \left\{3\right\}, \left\{4\right\}, \left\{1,3\right\}, \left\{1,4\right\}, \left\{2,4\right\}$
So $\displaystyle I_4=8$

So we want to find a recurrence relation for $\displaystyle I_n$. We can observe that given $\displaystyle I_{n-1}$, $\displaystyle I_n = I_{n-1} + P(n)$
Where $\displaystyle P(n)$ is the number of valid subsets that do not contain $\displaystyle (n-1)$.
But it is easily seen that $\displaystyle P(n) = I_{n-2}$, and so we get:

$\displaystyle I_n = I_{n-1} + I_{n-2}$ , as expected.

3. Originally Posted by Snowboarder
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.
Here is a way to see how the recursion works.
Let’s say $\displaystyle n\ge 3$. Any subset valid in $\displaystyle I_{n-1}$ would of course be valid in $\displaystyle I_{n}$.
Now subsets in $\displaystyle I_{n-2}$ do not contain the number $\displaystyle {n-1}$.
So if we form these unions, $\displaystyle J = \left\{ {\{ n\} \cup Y:Y \in I_{n - 2} \wedge Y} \text{ is valid}\right\}$ , that is we put $\displaystyle {n}$ into every valid set in $\displaystyle I_{n-2}$.
So now we have $\displaystyle a_{n}= a_{n-1}+a_{n-2}$.