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?

  • $\begingroup$ Do you understand why $a_0=1$? If you do, $a_1=2$ is pretty much the same. $\endgroup$ – Git Gud Feb 4 '14 at 13:26
  • $\begingroup$ @Git Gud does $a_0=1$ mean the empty series? so just one option? $\endgroup$ – 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.

  • $\begingroup$ but why does not this set has all 10 options for all digits? $\endgroup$ – user7777777 Feb 4 '14 at 13:36
  • $\begingroup$ "∅ or {1}" for what they stand for in this question? $\endgroup$ – user7777777 Feb 4 '14 at 15:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Feb 4 '14 at 16:13
  • $\begingroup$ @ Ross Millikan from your answer how can I see the expression $a_n=a_{n−1}+a_{n−2}$ $\endgroup$ – user7777777 Feb 4 '14 at 16:28
  • $\begingroup$ 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. $\endgroup$ – 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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.