A row in a classroom has n seats let sn be the number of

Question

Question: A row in a classroom has n seats. Let sn 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₃ = 4.) Find a recurrence relation for s₁, s₂, s₃,... .