# recursion-consecutive numbers

what is the number of subsets of the set {k∈N|1≤k≤n} with no two consecutive numbers? The answer says: $$a_n=a_{n-1}+a_{n-2}$$ with the starting conditions: $$a_0=1, a_1=2$$1. why does $a_1=2$?  2. How does this recursion was created, I understand that if $a_n$ mean all the places with no consecutive numbers so, $a_{n-1}$ come from the fact that after the first place all those places satisfy this condition, but why there is need to "look" at what happen after the two places?

• Do you understand why $a_0=1$? If you do, $a_1=2$ is pretty much the same. – Git Gud Feb 4 '14 at 13:26
• @Git Gud does $a_0=1$ mean the empty series? so just one option? – user7777777 Feb 4 '14 at 13:31

$a_1=2$ because if $n=1$ you can either have $\emptyset$ or $\{1\}$

For the recursion, to form a subset from $n$, you can either have a subset of $n-1$ and not take element $n$ or you can have a subset of $n-2$, not take $n-1$ and take $n$. You should convince yourself that this accounts for all the subsets of $n$ that don't have two in a row.

• but why does not this set has all 10 options for all digits? – user7777777 Feb 4 '14 at 13:36
• "∅ or {1}" for what they stand for in this question? – user7777777 Feb 4 '14 at 15:31
• First comment: we are not talking about digits, we are talking about numbers. If $n=6, \{1,3,6\}$ would be a legal subset, but $\{1,3,4,6\}$ would not because of the $3$ and $4$. Second comment: $\emptyset$ is the empty set. $\{1\}$ is the set with only $1$ as a member. For $n=1$, that is your set. These two are the legal subsets. – Ross Millikan Feb 4 '14 at 16:13
• @ Ross Millikan from your answer how can I see the expression $a_n=a_{n−1}+a_{n−2}$ – user7777777 Feb 4 '14 at 16:28
• In my second paragraph I show how to separate the legal subsets into two groups. The first are just the legal subsets taken from $n-1$, so there are $a_{n-1}$ of them. The second are in correspondence with the legal subsets taken from $n-2$, so there are $a_{n-2}$ of them. – Ross Millikan Feb 5 '14 at 21:23

Subsets of a set include the empty set, marked with $∅$ or $\{∅\}$.

• $n=0:$ The empty set $\{∅\}$ has one subset: $\{∅\}$. So $a_0=1$.
• $n=1:$ The set $\{1\}$ has 2 subsets: $\{1\}$ and $\{∅\}$. So $a_1=2$.

For a general $n$ you can decide that the first number is used or that it is not used in the subset.

• $1^{st}$ number not used: there are $n-1$ numbers left and $a_{n-1}$ subsets.
• $1^{st}$ number is used: we cannot take the number next to $1^{st}$ and we're left with $a_{n-2}$ possibilities.

Overall we combine these two alternatives to obtain the identity in question: $$a_{n}=a_{n-1}+a_{n-2}$$