From Susanna Epp's book:
A row in a classroom has $n$ seats. Let $s_n$ be the number of ways nonempty sets of students can sit in the row so that no student is seated directly adjacent to any other student. (For instance, a row of three seats could contain a single student in any of the seats or a pair of students in the two outer seats. Thus $s_3 = 4$.) Find a recurrence relation for $s_1, s_2, s_3, ...$
Here're the arrangements for rows from 1 to 5:
$s_1=1$ (1 way to place 1 student)
$s_2=2$ (2 ways to place 1 student)
$s_3=4$ (3 ways to place 1 student, 1 way to place 2 students)
$s_4=7=4+2+1=1+s_3+s_2$ (4 ways to place 1 student, 3 ways to place 2 students)
$s_5=12=7+4+1=1+s_4+s_3$ (5 ways to place 1 student, 6 ways to place 2 students, 1 way to place 3 students)
The pattern is clear: $s_n=1+s_{n-1}+s_{n-2}$ So the set of all arrangements of students in the current row can be partitioned to 3 subsets:
- some one one way to do something
- the number of ways to sit students in a row 1 sits less
- the number of ways to sit students in a row 2 sits less
Why does the partition looks like this? What is 1 and why $s_{n-1}$ and $s_{n-2}$?