# 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}$.
All times are GMT -8. The time now is 12:59 PM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 30, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.819327712059021, "perplexity_flag": "middle"}