[MUSIC] Welcome back. In this video I want to introduce another problem whose solution is the Fibonacci numbers. I call this problem climbing the staircase. So how do we pose the climbing the staircase problem. The question to answer is how many ways can one climb a staircase with n steps. Taking one or two steps at a time. So we have a staircase, we can go climb the staircase as one step, one step, two step, one step. Or we can climb it as two step, two step, one step. And if we have n stairs in the staircase, then how many different ways can we climb the staircase? To answer this problem we could make a table. We can consider a small number of stairs, from one to five stairs, and we can list the number of ways that we can climb this staircase. So, if there's only one stair there's only one way to climb this staircase, which is to go up by one stair. So we call a sub n the number of ways you can climb a n stair staircase. So a sub 1 is 1. If we have two stairs in the staircase, then we can climb 11. Or we can just climb 2, go up both stairs at the same time. So, a sub 2 then is equal to 2. If we have a 3 stair staircase, we can go 111, 12, go two stairs at a time at the end, or we can go two, one, two stairs at the beginning. And there are three different ways we can climb a three stair staircase. So we have one, two, three, looks like we're just counting, right? But if we have a four step staircase, that in fact there are five different ways, 1111, 112, 121, 211 and finally 22. We take two stairs first and then we take two more stairs. So there are five different ways to climb a four step staircase. So now we have the sequence 1, 2, 3, 5. Five is equal to two plus three so it's part of the Fibonacci sequence. Let's look at one more. What if we have five stairs in the staircase. Then if we list out all the possible ways to claim a five stair staircase we see that there are eight different ways. So now we're getting the Fibonacci sequence here. 1, 2, 3, 5, 8 just missing the first one. So why are we getting the Fibonacci sequence, can we do some sort of mathematical argument to show you that we should have the Fibonacci sequence. So let me try and do that. So, let's think about how to climb the staircase. We can actually break climbing of the staircase into two different ways. We can start by climbing the first stair. We can climb by one stair, right? And then so on climb the rest of the staircase, okay? The other way is we can start with two stairs, so we can start with two stairs and then climb the rest of the staircase. So we have those two possibilities. The first step we take can be one stair or the first step we take that can be two stairs. So how many ways are there then to climb n stairs, staircase if the first step we take is one stair. While there's n minus one stairs left, right? We took one step already, there's n minus 1 steps left. So the number of ways we can climb at n stairs staircase here is n- 1 ways because we've already climbed the first step. The number of ways we can climb and n stair staircase if we take as our first step, two steps, is the number of ways we can climb n minus 2 steps because we already took 2 steps. So the number of ways here is, a sub n- 2, okay? So the argument I'm making is that the number of ways to climb an n stair staircase is equal to a number of ways to climb that staircase where the first step is one step. A sub n- 1, plus the number of ways to climb a staircase. Where the first step is two steps, a sub n- 2. A sub n = a sub n- 1 + a sub n- 2. That's just the recursion relation for the Fibonacci sequence. That's why we're getting Fibonacci numbers. The difference though is we need the initial conditions, so the initial values, so the number of ways to climb a one step staircase is one right? The number of ways to climb a two steps staircase. Remember it's 1, 1 or just 2, so that's 2. So these are not the initial values for the Fibonacci sequence but 2 is a unique Fibonacci number, is the third Fibonacci number, and one can be the second Fibonacci or the first Fibonacci number. Here I take it to be the second Fibonacci number. So a sub 1 is F sub 2, a sub 2 is f sub 3. a satisfies the Fibonacci recursion relation so we must have a sub n as a Fibonacci number but it's not F sub n, it's one more than F sub n, it's F sub n + 1, okay? So the number of ways to climb an n step staircase taking one step or two step at a time is the n+1 Fibonacci numbers. Fibonacci numbers showed up in this problem. So we've seen now two problems with Fibonacci numbers. The rabbit plot problem, the classic rabbit problem from Fibonacci and the climbing the staircase problem. In the next lecture, I want to talk about the golden ratio. And then we'll find a connection between the golden ratio and the Fibonacci numbers. I'll see you next time.
