Fibonacci Sequence and Climbing Staircase problem

Hello Friends, So here is our next blog on Fibonacci  Sequence. In this blog I will introduce another problem whose solution is the Fibonacci Number. This problem is known as Climbing Staircase problem.

The Question is How many ways one can climb staircase with n steps, taking one or two steps at a time ??

Questions Of Climbing Staircase 

Eg.

Suppose we have 3 steps to climb.

So we have a Staircase, we climb it by taking one step , one step , one step or two step , one step or one step, two step.

So If we have n-steps in Staircase , then how many different ways can we climb the Staircase?

So to answer this question we could make a table, considering small numbers of steps i.e n = 1,2,3,4,5

And we can list the number of ways to climb the Staircase. So Observe the table first column is number of stairs or steps. Second column is the list of ways one can climb by taking one or two steps at a time. Third column a_n  the total number of ways to climb Staircase. I hope you understood till here if not observe the table you will understand definitely.

Ways to climb stairs 

By Observing the above table's third column  "a_n" you can see the fibonacci number are appearing. As the number of steps increases the answer is just the sum of previous two total number of ways . So here we got Fibonacci Sequence 1,2,3,5,8,13,21...

So why we are getting Fibonacci Sequence here can we do some sort of mathematical argument to reach the same result ? So let's give it a try. Because trying is what we can always do.

 So let's think about it again how to climb the Staircase taking one or two steps at a time. Did you get some lead ?  If you observe for the first step it is either one step or two right . So we can break it into two different ways. So n steps are there if you take your first step as one so left step to climb is n-1 right. If you take first step as 2 then left steps to climb is n-2 because we already climb 2 step.

Argument here is if you take first step as 1 then rest n-1 steps can be climbed as a_n-1. 

Or 

If first step is 2 then rest n-2 steps can be climbed as a_n-2 I hope you know what is a_n  if not go through the ways to climb table ones more.

And through logic the number of ways two climb n stairs Staircase is equal to a number of ways to climb that staircase where the first step is one step i.e. a_n-1 , Plus the number of ways to climb the Staircase when the first step is two step i.e. a_n-2 .

So we have 

 

                         a_{n =} a_{n-1 +}  a_n-2   

Which Is the recursion relation of Fibonacci Sequence that's why we are getting Fibonacci numbers. 

The difference though is we need the initial condition, so the initial values. We know that from table to climb one step Staircase there is only 1 way and to climb two steps Staircase there are 2 ways either 1,1 or 2 right. But this are not initial values of Fibonacci Sequence in fact 2 is unique Fibonacci number, which is 3rd Fibonacci number, and 1 can ce first Fibonacci number or second Fibonacci number. 

            a1=1=F2  

            a2=2=F3 

So we can say here   a_n=Fn+1

So the number of ways to climb an n steps staircase taking one or two steps at a time is n+1 Fibonacci number.

We have seen now two problems with Fibonacci number. The classic Rabbit population problem from Fibonacci and the Climbing Staircase problem. 

In Our Next Blog we will discuss about the GOLDEN RATIO. The connection between Fibonacci Number and Golden Ratio.