Number of ways to color a sequence of squares so that no two black squares are adjacent

Question

A sequence of squares may be colored so that each square is black or white. Let $S_n$ be the number of ways of coloring the sequence so that no two black squares are adjacent. Find a recursive relation for $S_n$.

Progress

$S_1= \{b,w\}$, $S_2=\{bw,wb,ww\}$, ... $S_3=\{bww,bwb,wbw,www,,wwb,\}$... This is what I have so far. Not even sure if it's correct.. this is new to me.

Answer 1

S1: (b),(w) =2 .....S2:(b,w),(w,w),(w,b)=3.....S3: (w,w,w),(w,b,w)(w,w,b),(b,w,w), (b,w,b)=5

case 1: A valid sequence of n−1 squares followed by a white square; case 2: valid sequence of n−2 squares followed by a white and then a black square.

Sn=Sn-1 + Sn-2

initial conditions : 2, when n=1..3 when n=2 when n>=3

Answer 2

Next time, you should indicate your thoughts on the problem along with the questions.

You can approach this problem in the following way: given a valid sequence (valid meaning without two adjacent black squares) of length $n$, how can this sequence look like? Observe that it can either be

1. A valid sequence of $n - 1$ squares followed by a white square;
2. A valid sequence of $n - 2$ squares followed by a white and then a black square.

Giving us the nice Fibonacci pattern: $$ S_n = \underbrace{S_{n - 1}}_{\text{first case}} + \underbrace{S_{n - 2}}_{\text{second case}} $$

I'll leave the initial conditions ($S_1$ and $S_2$) to you.