Medium | Discrete Maths |

A rabbit sits at the bottom of a staircase with n stairs. The rabbit can hop up only one or two stairs at a time. What kind of sequence is depicted by the different ways possible for the rabbit to ascend to the top of the stairs of length n=1,2,3...?

Hint

Recursion

Answer

Fibonacci Sequence.

Solution

Suppose f(n) are the number of ways to reach nth stair. Notice that the final hop is either a single jump or double jump, i.e. its from (n-1)th stair or (n-2)th. Thus f(n) = f(n-1) + f(n-2), where f(0)=f(1)=1. This is Fibonacci sequence.

Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |