recursion-consecutive numbers

Question

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?

Answer 1

$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.

Answer 2

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}$$