using System;
class SumFibonacciRangeClass
{
// 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
static ulong Fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
ulong prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
ulong next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
// Function to calculate sum of Fibonacci numbers from index L to R (inclusive)
static ulong SumFibonacciRange(int L, int R) {
// 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);
}
static void Main()
{
int left = 2, right = 8;
ulong result = SumFibonacciRange(left, right);
Console.WriteLine("Sum of Fibonacci numbers from index {0} to {1} = {2}", left, right, result);
}
}
/*
run:
Sum of Fibonacci numbers from index 2 to 8 = 53
*/
