CODEWITHSUNDEEP
pythonfibonaccifactorial
codinggosu
codinggosu

Reputation: 35

Calculating the nth Fibonacci number with a sum of factorials?

During my efforts to solve leetcode 70, climbing stairs, I thought of an answer that uses factorials (how many different ways to form a line with identical elements). Later, I thought that the question could also be solved using fibonacci, and the first few answers appear to be the same.

My questions are: Is there a formal mathematical proof (or an intuitive explanation) as to why these two might be the same? or if they are the same?

the climbing stairs problem is a problem that asks you to find the number of ways a person only taking one or two steps can climb up a stair with n stairs. Since this is just a way of saying how many different ways can you line up 1 and 2 that sum up to n. I solved the questions that way. max_one, and max_two are maximum numbers of 1s or 2s that can exist and I iterated over how many 2s could be in the line, finding how every different line can be formed given number of 2s (represented as i) the numerator is how many elements in line, the denominator is how many identical elements ( how many 1s, how many 2s) are in the line:

from math import factorial as fac
class Solution:
  def climbStairs(self, n):
    if n == 1:  return 1
    if n == 2:  return 2 
    max_two = n//2
    max_one = n
    ways = 0
    for i in range(0,max_two+1):
      ways += fac(max_one-i)/(fac(max_one-2*i) * fac(i))

    return int(ways)

Upvotes: 2

Views: 696

Answers (1)

templatetypedef
templatetypedef

Reputation: 372814

Congratulations! You’ve rediscovered a very cool identity involving the Fibonacci numbers. Specifically, the rule you’ve found is what’s visually demonstrated in this picture, where adding up terms of Pascal’s triangle along these skew diagonals gives back the Fibonacci sequence:

adding skew diagonals for fun and profit

To see why this is, notice that each term in your summation is equal to (n - i) choose i, which is the entry in row (n - i), column i of Pascal’s triangle. Each term in the summation corresponds to moving up one row and over one column, hence the angle on those lines.

As for a proof, the argument that you’ve outlined is essentially the basis of a double-counting argument. We know that the Fibonacci numbers count the number of ways to walk down a flight of stairs taking steps of sizes one and two, which we can rigorously prove by induction. Additionally, we know that your summation counts the same quantity, as you’re enumerating all the ways to take paths down using 0, 1, 2, 3, ..., etc. steps of size two. Since we’re counting the same quantity in two ways, these two expressions must be equal.

If that doesn’t suffice, you can formalize this using a proof by induction, using the identity (n choose k) = (n-1 choose k) + (n-1 choose k-1) and splitting into cases where n is even and where n is odd.

Hope this helps!

Upvotes: 1

Related Questions