# Example: left = 2, right = 8
# Explanation: F(2) + F(3) + F(4) + F(5) + F(6) + F(7) + F(8) = 1 + 2 + 3 + 5 + 8 + 13 + 21 = 53
# Function to compute Fibonacci numbers up to n
def fibonacci(n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
prev, curr = 0, 1
for i in range(2, n + 1):
next_val = prev + curr
prev, curr = curr, next_val
return curr
# Function to calculate sum of Fibonacci numbers from index L to R (inclusive)
def sum_fibonacci_range(L: int, R: int) -> int:
# If the range is invalid (e.g., L > R), return 0
if L > R:
return 0
"""
Mathematical identity:
Sum(F_L + F_(L+1) + ... + F_R) = F_(R+2) - F_(L+1)
Explanation:
- The sum of the first n Fibonacci numbers is F_(n+2) - 1.
- So, the sum from F_L to F_R can be derived by subtracting:
(sum of first R terms) - (sum of first (L-1) terms)
= (F_(R+2) - 1) - (F_(L+1) - 1)
= F_(R+2) - F_(L+1)
"""
return fibonacci(R + 2) - fibonacci(L + 1)
if __name__ == "__main__":
left, right = 2, 8
result = sum_fibonacci_range(left, right)
print(f"Sum of Fibonacci numbers from index {left} to {right} = {result}")
"""
run:
Sum of Fibonacci numbers from index 2 to 8 = 53
"""
