You are familiar with the Fibonacci sequence from various places *f *(1)=1 Equ 1 *f *(2)=1

*f *(*n*)=*f *(*n*−1)+*f *(*n*−2).

Let’s define a sum as *S*(*n*)=*f *(0)+*f *(1)+⋯+*f *(*n*). This assignment involves experimenting with various approaches to compute *S *(*n*), as well as, demonstrating various algebraic techniques for recursive definition.

# Tasks for this assignment

- Write a program to calculate
*S*(*n*) by calculating the values of the Fibonacci sequence recursively. - Write a non-recursive program to calculate
*S*(*n*). This second program uses the recurrence definition to calculate and TABULATE the values of the Fibonacci sequence. Then, sum these values to find*S*(*n*). *Discrete & Combinatorial Mathematics*by Ralph Grimaldi outlines a method to obtain the solution

*n g*.

Algebraically verify that *g *(*n*) is a solution of Equ 1 by substituting *g *(*n*) in Equ 1.

- From task #3, there is now a third method to calculate
*S*(*n*). Write a third iterative program by

*k *summing: *S*.

- Use your preferred program to calculate these values of
*S*for*n*= 10, 20, 30. Also, compute these values of*f*for*n*= 12, 22, 32. - Task #7 suggests that
*S*(*n*)=*f*(*n*+2)−1. Prove this identity (using induction). - Finally, there is yet a fourth way to programmatically calculate
*S*(*n*). - Experiment with your programs to estimate the largest
*n*that can be computed__successfully__by each program. - Experiment & run the recursive program for several sufficiently large values of
*n*. Execute the other three programs with the same values of*n*& compare the execution times of the 4 programs. - Write your report and show a demo of your second program. The report should include a summary of your work, a summary & conclusion of your experiments and the results of the experiments, as well as the algebraic work and a printout of your program. What are the advantages or shortcomings of each computation?

You are familiar with the Fibonacci sequence from various places *f *(1)=1 Equ 1 *f *(2)=1

*f *(*n*)=*f *(*n*−1)+*f *(*n*−2).

Let’s define a sum as *S*(*n*)=*f *(0)+*f *(1)+⋯+*f *(*n*). This assignment involves experimenting with various approaches to compute *S *(*n*), as well as, demonstrating various algebraic techniques for recursive definition.

## Reviews

There are no reviews yet.