Fibonacci Sequence Exploration — Patterns, Proofs, Code

The Sum of the First N Fibonacci Terms

The Sum of First N Fibonacci Terms With Odd Indices

The Sum of First N Fibonacci Terms With Even Indices

Nth Fibonacci Term Coding Question

Recursive Solution

def nth_fibonacci(n):
if (n <= 1):
return 1
else:
return nth_fibonacci(n - 1) + nth_fibonacci(n - 2)

Time Complexity Analysis

Memoization/Dynamic Programming Solution

def fib(self, n: int) -> int:
#Initialize first two terms
dp = [0,1]
if n < 2:
return dp[n]
for i in range(1,n):
dp.append(dp[i]+dp[i-1])
return dp[-1]

Time and Space Complexity Analysis

Space Efficient Fibonacci DP Solution

def fib(self, n: int) -> int:
#initialize length 3 array
dp = [0,1,0]
if n == 0:
return dp[0]
elif n == 1:
return dp[1]
else:
for i in range(1,n):
dp[2] = dp[0]+dp[1]
dp[0] = dp[1]
dp[1] = dp[2]
return dp[2]

Time and Space Complexity Analysis

Constant Time Fibonacci Solution

def fib(self, n: int) -> int:
p = (1 + math.sqrt(5)) / 2
return round(p**n/math.sqrt(5))

Fibonacci Sums With Code

First N Terms Sum

def fib_sum(n):
return fib(n+2) - 1

First N Terms Sum Odd Indices

def fib_odd_sum(n):
return fib(2*n)

First N Terms Sum Even Indices

def fib_even_sum(n):
return fib(2*(n+1))-1

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store