When building a wall all the bricks in a row should be

Question

Question: When building a wall, all the bricks in a row should be directly next to each other and every brick should be set on top of exactly two other bricks. A few stacks of bricks are shown in Figure. We shall denote the number of different stacks of bricks with n bricks along the bottom by bn.

(a) What are the first few brick-stack numbers b₁, b₂, b₃, b₄?

(b) Construct a recurrence for bn and explain why it is correct.