Discrete Mathematics
# Introduction to Recursion

Using 1'' x 2'' dominoes, there's one way to tile a 1'' x 2'' area, 2 ways to tile a 2'' x 2'' area, and 3 ways to tile a 3'' x 2'' area.

How many ways are there to tile a 4'' x 2'' area?

Nine plots of land are arranged in a circle. Each plot of land has a flower planted on it. A farmer, starting from one of the plots decided to clear all the plots, but in a peculiar way:

- To start, the farmer moves one plot clockwise around the circle and clears that plot of land, then moves two plots clockwise and clears it, then moves three plots clockwise and clears it, and so on.
- If the farmer arrives at a plot of land which he has already cleared, then he will plant a flower there.

How many times would the farmer have circled around all 9 plots of land before he would have cleared all the plots of land?

Bombus the BumbleBee wants to get to the cell containing honey.

Each time, he can only take a step to a neighboring cell, that moves him to the right.

How many ways does he have of reaching the honey in the last cell?

The image above shows a construction of fractal by joining smaller and smaller squares to each side of one single square.

- We start with a square of side length 3.
- In the second figure, the 4 new squares are formed with a side length of $\dfrac{1}{3}$ of its previous square.
- Then from the third figure and so on, the new squares can only be formed on the 3 sides of the previous squares with side length $\dfrac{1}{3}$ of its previous square.

As this recursion continues indefinitely, what does the total area of the figure tend to?

How many unit squares are there in the next square in this spiraling sequence?