The valid subsets and reccurence relation

Printable View

August 24th 2009, 10:36 PM
Snowboarder

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
August 25th 2009, 01:53 AM
Defunkt

$k=0:$
The empty set matches the criteria, so $I_0 = 1$

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

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

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

$k=4:$
$\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 $I_4=8$

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

$I_n = I_{n-1} + I_{n-2}$ , as expected.
August 25th 2009, 06:49 AM
Plato

Quote:

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 $n\ge 3$ . Any subset valid in $I_{n-1}$ would of course be valid in $I_{n}$ .
Now subsets in $I_{n-2}$ do not contain the number ${n-1}$ .
So if we form these unions, $J = \left\{ {\{ n\} \cup Y:Y \in I_{n - 2} \wedge Y} \text{ is valid}\right\}$ , that is we put ${n}$ into every valid set in $I_{n-2}$ .
So now we have $a_{n}= a_{n-1}+a_{n-2}$ .