1

Find a recurrence relation for the number of ways to select a subset (any size, including the empty set) from the set {1,2,3, … ,n} that does not contain a pair of consecutive numbers?

Would this problem be similar to induction? not sure how to apply it to recurrence in this case.

user142743
  • 127
  • Related: http://math.stackexchange.com/questions/490405/choosing-numbers-without-consecutive-numbers also http://math.stackexchange.com/questions/734253/number-of-subsets-without-consecutive-numbers also http://math.stackexchange.com/questions/761293/probability-of-no-consecutive-numbers also http://math.stackexchange.com/questions/603641/k-element-subsets-of-n-that-do-not-contain-2-consecutive-integers – Gerry Myerson May 04 '14 at 01:12

1 Answers1

1

Denote the number of subsets of the given type $K_n$ for $n$.

The question is looking for an expression for $K_n$, using perhaps previous $K_m$'s (with $m<n$).

Now, we have $K_0=1,\ K_1=2,\ K_2=3$.

Then, for a general $n$, to lead it back to $n-1$, we count the subsets in two turns: first those which does not contain the last element, $n$: the number of these is exactly $K_{n-1}$. The rest contain $n$, but then they cannot contain $n-1$. The number of these is $K_{n-2}$.

So, if $S$ is a subset that contains $n$, then $S\cap\{1,2,\dots,n-1\}$ is any subset of $\{1,2,\dots,n-2\}$ that still doesn't contain a consecutive pair.

All in all, we get the recursion $$K_n=K_{n-1}+K_{n-2}\,.$$

Berci
  • 90,745