Recurrence Relations · Recursive Definitions

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

It is easy to see that the sequence \(B(n)\) satisfies the recurrence relation \[B(0)=1,\ B(1)=1, \ B(n)=B(n-1)+B(n-2) \ .\] This can be explained by considering two cases for how the bottom-left corner of the strip is covered:

  1. If it is covered by a horizontal domino, then the rest is a tiling of a \((n-1) \times 2\) strip;
  2. If it is covered by a vertical domino, then the bottom-right corner is also covered by a vertical domino, and the rest is a tiling of a \((n-2) \times 2\) strip.
The recurrence relation for \(B(n)\) differs from that of Fibonacci numbers only in the initial conditions, so \(B(n)=F(n+1)\).