Solving number of subsets that meet the “spread out” condition using recurrence relation

Question

I'm trying to follow the solution shown here from (lulu):

Number of subsets that meet the "spread out" condition

Lulu then says in one of the comments that this can be solved as a recurrence relation and that the correct recurrence relation is:

$A_n = A_{n-1} + A_{n-3}$

How many such subsets are there (you can list and count them) for S={1,2,3}? For S={1,2,3,4}? And so on. Do you see a pattern in the answers?

S={1,2,3} = $\varnothing,\{1\},\{2\},\{3\}$ $A_3 = 4$

S={1,2,3,4} = $\varnothing,\{1\},\{2\},\{3\},\{4\}, \{4,1\}$ $A_4 = 6$

S={1,2,3,4,5} = $\varnothing,\{1\},\{2\},\{3\},\{4\},\{5\},\{4,1\},\{5,1\}, \{5,2\}$ $A_5 = 9$

S={1,2,3,4,5,6} = $\varnothing,\{1\},\{2\},\{3\},\{4\},\{5\},\{6\},\{4,1\},\{5,1\},\{5,2\},\{6,1\},\{6,2\},\{6,3\} $ $A_6 = 13$

S={1,2,3,4,5,6,7} = $\varnothing,\{1\},\{2\},\{3\},\{4\},\{5\},\{6\},\{7\}\{4,1\},\{5,1\},\{5,2\},\{6,1\},\{6,2\},\{6,3\},\{7,1\},\{7,2\},\{7,3\},\{7,4\} $ $A_7 = 18$

For $A_6$ the recursion works $A_6= A_5 + A_3$

However $A_7$ does not. Accorsong to the furmuls it shouyld be 19 but I can only find 18 valid combinations? Have I gone wrong?

Answer 1

Such problems can usually be tackled by "distinguishing" an element, and looking at the cases in which it is included and in which it isn't. The number $A_n$ of subsets of $\{1, \dotsc, n\}$ with the given condition is one of:

• A subset containing $n$: Then it can't contain $n - 1$ nor $n - 2$, the remainder is one of the $A_{n - 3}$ subsets of $\{1, \dotsc, n - 3\}$
• A subset that doesn't contain $n$: This is just one of the $A_{n - 1}$ subsets of $\{1, \dotsc, n - 1\}$

In all, $A_n = A_{n - 1} + A_{n - 3}$.

Need a few values to start the recurrence. Clearly $A_0 = A_1 = 1$, $A_2 = 0$.