Let's look at Fibonacci. The sequence starts with 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

So, the first two values are: fib(0) = 0, fib(1)=1

After that, the next fib number is the sum of the previous two, So, fib(2) = fib(0) + fib(1), fib(3) = fib(2) + fib(1), etc.

© 2024 Praveen Puri

I saw an online discussion of someone wanting to sum the first N Fibonacci sequence, and looking for an efficient recursive program.

I wondered if you even needed recursion for the sum since, when you are summing integers, you can do it without a loop or recursion. The sum of the first N integers is N(N+1)/2

So, I dug in and found that you can sum the first N Fibonacci numbers without loops or recursion.

**1.**First, we can define the constant phi = (1 + sqrt(5))/2 #1 plus the square root of 5, divided by 2

**2.**Next, we can create a function to calculate the nth Fibonacci number without loops or recursion:

fib(n) = int_round_up {[ phi ^ n - (-1 / phi) ^ n ] / sqrt(5) } # do the calc in decimal and round up to int

**3.**Finally, the function to find the sum of the first N Fibonacci numbers:

Sum_fib(n) = fib(n+2) - 1 # The sum of the first N Fib numbers is just the N+2 Fib number - 1

So, it turns out finding the sum of Fibonacci numbers is actually a simple, elegant process.

© 2024 Praveen Puri