# How many subsets contain no 3 consecutive elements?

How many subsets of $$\{1,2,...,n\}$$ have no $$3$$ consecutive numbers ?

## My solution:

Inspired by How many subsets contain no consecutive elements? I decided to write recurrence: Let be set with numbers from $$1$$ to $$n$$ and let $$A$$ - subset of given set $$a_n = \underbrace{a_{n-1}}_{n \notin A} + \underbrace{a_{n-2}}_{n \in A , n-1 \notin A} + \underbrace{a_{n-3}}_{n \in A, n-1 \in A, n-2 \notin A}$$

After examining corner cases I use iverson bracket to write full recurrence: $$a_n = a_{n-1}+ a_{n-2} + a_{n-3} + [n=0] + [n=1] + [n=2]$$ After multiplying by $$x^n$$ and summing by all $$n$$ I got generating function: $$A(x) = x A(x) + x^2 A(x) + x^3 A(x) +1+ x + x^2$$ $$A(x) = \frac{1+x+x^2}{1-x-x^2-x^3}$$ But how to solve this generating function to get coefficient with $$x^n$$?

• The characteristic polynomial for the recursion is $x^3-x^2-x-1$ and that hasn't got very pleasant roots, so there might not be a terribly good looking solution. – lulu Aug 24 at 20:58
• @lulu Before posting I also checked in mathematica so I am not sure if my approach is correct so decided to share that to forum with my explanation, maybe there is logical mistake there – Tester1998 Aug 24 at 20:59
• Oh, I trusted your recursion. But it looks correct...is there any reason you expected a pleasant solution? – lulu Aug 24 at 21:00
• This exercise comes from old exam, per task is about ~30 minutes so I wonder if there exists anything pleasant but I have doubts too... – Tester1998 Aug 24 at 21:03
• Not sure your initial conditions are correct. You seem to have $a_1=1, a_2=2$ but that's not correct. None of the $4$ subsets of $\{1,2\}$ contain $3$ consecutive terms – lulu Aug 24 at 21:03

The recursion: $$a_n=a_{n-1}+a_{n-2}+a_{n-3}\quad a_1=2\quad a_2=4 \quad a_3=7$$
has characteristic polynomial $$x^3-x^2-x-1$$ which doesn't have particularly pleasant roots, which means that there isn't a simple closed formula for the results. The sequence $$\{a_n\}=\{2,4,7,13, 24, 44, 81, \cdots \}$$ is part of A000073 in oeis.org and that link contains a lot of information on the sequence, though of course it does not present a simple closed formula. Note that the characterization given there as the number of binary sequences of length $$n$$ for which the string $$000$$ does not appear is entirely equivalent the one given by the OP here, as each string corresponds to a subset (where a $$1$$ indicates that the entry is absent and a $$0$$ indicates that it is present).