4
$\begingroup$

Given a set $X=\{1,2,\ldots,n\}$, how would I count the number of subsets containing only nonconsecutive elements?

For example:

$X=\{1,2,3,4\}$

implies 3 nonconsecutive subsets:

$\{1,3\}, \, \{2,4\}, \, \{1,4\}$

$\endgroup$
11
  • $\begingroup$ Doesn't $\{1,3,4\}$ contain $3,4$ which are consecutive? $\endgroup$
    – b00n heT
    Jan 30, 2017 at 16:16
  • 4
    $\begingroup$ As a hint, these subsets would either contain 1 or not. The subsets containing 1 would not contain 2, but anything from 3 on out would be allowed (as long as they're still not consecutive). The subsets not containing 1 could contain anything from 2 on out (again, as long as they're still not consecutive). This leads to a recurrence relation, which will likely be familiar to you. $\endgroup$
    – Rus May
    Jan 30, 2017 at 16:19
  • $\begingroup$ Why did you count $\{1,3,4\}$ but not $\{1,2,4\}$? $\endgroup$
    – MJD
    Jan 30, 2017 at 16:24
  • $\begingroup$ @MJD Yes, a typo. Fixed. $\endgroup$ Jan 30, 2017 at 16:27
  • 1
    $\begingroup$ Why did you count $\{1,2,4\}$ but not $\{1,3,4\}$? $\endgroup$
    – MJD
    Jan 30, 2017 at 16:28

1 Answer 1

3
$\begingroup$

Let $f_1(x)$ be the number of ways to pick a subset of numbers from $\{1,2,\cdots,x-1,x\}$ such that the set does not contain 2 consecutive elements and must contain $x$. Let $f_2(x)$ be defined similarly but instead the subset must not contain $x$.

We can see that $f_1(x+1) = f_2(x)$ since if the subset contains $x+1$, it cannot contain $x$

Also, $f_2(x+1) = f_1(x) + f_2(x)$ as you can choose to add $x$ into the subset or not

We also know that $f_1(1) = 1$ and $f_2(1) = 1$

Simplifying:

$$ \begin{align} f_2(x+1) &= f_1(x) + f_2(x)\\ &= f_1(x-1) + 2f_2(x-1)\\ &= 2f_1(x-2) + 3f_2(x-2)\\ &= 3f_1(x-3) + 5f_2(x-3)\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ &= F_x + F_{x+1}\\ &= F_{x+2} \end{align} $$

$$ \begin{align} f_1(x+1) &= f_2(x)\\ &= f_1(x-1) + f_2(x-1)\\ &= f_1(x-2) + 2f_2(x-2)\\ &= 2f_1(x-3) + 3f_2(x-3)\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ &= F_{x-1} + F_{x}\\ &= F_{x+1} \end{align} $$

where $F_x$ is the $x$th Fibonacci Number.

Thus $f_1(x) + f_2(x) = F_x + F_{x+1} = F_{x+2}$

$\endgroup$
1
  • $\begingroup$ Makes great sense. Accepted. $\endgroup$ Feb 1, 2017 at 16:06

Not the answer you're looking for? Browse other questions tagged .