Help; What exactly is this recursion method Prof. Loh is advocating for here?
-
Module 3 Week 3 Day 10 Challenge Part 3
What exactly is this recursion method Prof. Loh is advocating for here? Because he seems to say one thing and goes on to the next without finishing that first thing's description.
-
@The-Blade-Dancer Thank you for asking; Prof. Loh's explanation was rather quick at the end, and it is well worth explaining again!
At the beginning, he is saying that the method of listing cases depending on the number of rectangles (starting from 1 rectangle, then 2 rectangles, then 3 rectangles, etc.) can be very time-consuming and involve lots of error-prone arithmetic. Enter the recursion method! It's faster, easier, and less prone to error. Of course we should use recursion instead! All we have to do is understand it first.
Now, we're not going to concern ourselves with how many rectangles are in the tile. Instead, we're going to see that there is a very simple way to "grow" a tile: you can either add one square to the end or add one rectangle to the end. (These are the two cases mentioned below, around timestamp 3 minutes.)
To make a \(1 \times n\) strip, we can either add a square to the end of a \(1 \times (n-1)\) strip or add a rectangle to the end of a \(1 \times (n-2)\) strip. Thus we can write$$ a_n = a_{n-1} + a_{n-2},$$
which means the number of ways to tile a \(1 \times n\) strip is equal to the ways to tile a \(1 \times (n-1)\) strip plus the ways to tile a \(1 \times (n-2)\) strip.
Now, how does this relate to the next screen that he shows, with the Fibonacci numbers?
It just happens that the formula for the Fibonacci numbers matches exactly the formula for tiling a \( 1 \times n\) strip using only squares and \(1 \times 2\) rectangles! The \(n^{\text{th}}\) Fibonacci number is equal to the number of ways to tile a \(1 \times n\) strip in this way.
To see this visually, let's start with tiling some short strips of given length. In order to make a \(1 \times 3\) strip, we can add either a square to a \(1 \times 2\) strip or add a rectangle to a \(1 \times 1\) strip.
$$ a_3 = a_2 + a_1 $$
In order to make a \(1 \times 4\) strip, we can either add a square to a \(1 \times 3\) strip or add a rectangle to a \(1 \times 2\) strip.
$$ a_4 = a_3 + a_2 $$
In order to make a \(1 \times 5\) strip, we can either add a square to a \(1 \times 4\) strip or add a rectangle to a \(1 \times 3\) strip.
$$ a_5 = a_4 + a_3 $$
This is exactly the pattern in the Fibonacci sequence! To get any number in the Fibonacci sequence, you just add the previous two numbers. So all we have to do in order to find the ways to tile a \(1 \times 7\) strip is to write out the Fibonacci sequence, look up the \(7^{\text{th}}\) number, and wha-la! This is our answer! The answer is \(\boxed{21}.\)
