How many subsets of $\{1,2,…,n\}$ do not contain three consecutive integers

combinatoricselementary-number-theory

My attempt. Let us assume $n$ is a large positive integer. ${n \choose 0},{n \choose 1},{n \choose 2}$ are the numbers of such subsets having $0,1,2$ elements respectively, which is trivial. For $3$ elements, the number of such subsets is ${n \choose 3}-(n-2)$. Starting from $4$ elements, my brain begins muddling up; I have no idea how to proceed further systematically. Any hint or idea would be appreciated.

Remark. Thanks to the partial solutions by VIVID and Masacroso, I have completely solved this problem. Following VIVID's answer, I have posted an answer which completes the solution primarily for future reference.
I am going to give the accepted answer to VIVID who has been very dedicated to this problem seen from his number of edits. Also, most importantly, VIVID was the first person who posted the core part of the solution. Masacroso, hope you would not mind.

Last, though this problem has been completely resolved, any new approach is always welcome.

Best Answer

Partial solution: Let's denote by $S \subseteq \{1,2,\dots,n\}$ all sets that satisfy the condition. And let $a_n$ be the number of such sets.

There may be some cases:

  1. $n \not \in S \implies$ there are $a_{n-1}$ possibilities for $S$ (clear)
  2. $n \in S$:
  • a) $n-1 \not \in S \implies$ there are $a_{n-2}$ possibilities for $S$ (why?)
  • b) $n-1 \in S, \ \ n-2 \not \in S \implies$ there are $a_{n-3}$ possibilities for $S$. (why?)

Hence, we get the recurrence formula $$\boxed{a_n = a_{n-1} + a_{n-2} + a_{n-3}}$$

Answer two (why?) parts above and it will become a full solution.

Related Question