Question

You have 2 floors, and there are 14 steps inbetween the two floors. you have a cat that can get to the top by either taking one step at a time or two steps. ( at one time going up the cat can take both one or two steps). How many possible combinations are there for the cat to get to the top?

Answer 1

Let f (n) - the number of options that a cat can pass through n steps. On the n - th step can proceed or (n - 1) - th, or (n - 2) - th. Number of options to pass n is the number of steps to pass the options n - 1 steps plus the number of options to pass n - 2 steps, that is f (n) = f (n - 1) + f (n - 2). It is obvious that f (1) = 1 and f (2) = 2. Thus f (n) is (n + 1) - th Fibonacci number.

1,1,2,3,5,8,13,21,34,55,89,144,233,377,
610<-- 15-th Fibonacci number