My Board My Chalk

  This article is in continuation of  this one . R ecap In the  previous article , I had tried to emphasize how nᵗʰ Fibonacci Number = Number of ways to climb n step staircase, where you have only two possible options to move, either by climbing 1 step or 2 steps at a time. In the same article, I have mentioned some other  p ossible representations of the Fibonacci Sequence. One of them is the number of ways to tile a N x 1 board with a 1 x 1 square and 2 x 1 domino. By writing the recurrence relation for the same, we can state that NoOfWaysToTile(n) = nᵗʰ Fibonacci Number. Recurrence for the Tiling problem Tiling Problem Relation and Fibonacci Number Reversing the above Equation In this article, I am going to discuss my approach to the Running Sum Identity of the Fibonacci Sequence using the same relation. The Running Sum of Fibonacci Sequence The Left Hand Side (L.H.S.) The L.H.S. of the equation has 2 parts  Fib(n)  and  (- 1) . Fib(n) = nᵗʰ Fibonacci Number = No of ways to tile n x

  Climbing Staircase Problem T he Story begins with a Problem Yesterday, I was solving a very famous DP problem,  the climbing stairs . The problem is quite simple. You are climbing a staircase. It takes  n  steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Solution The solution is also pretty straight forward. Suppose we have climbed up some steps and we are left with some  i  steps to reach the top. Let’s say,  NoOfWays(i)  be a function that returns the number of ways to climb  i  steps to reach the top. If we climb by 1 step, then we are left with (i-1) steps. Using the above formula, the number of ways to climb (i -1) steps = NoOfWays(i-1). Similarly, if we climb by 2 steps, then we are left with (i-2) steps, and using the formula, the number of ways to climb (i -2) steps = NoOfWays(i-2). Since we can climb in one of the two fashions only so the number of ways to climb  i  steps is given as follows For the b