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

f (n)=f (n1)+f (n2).

Lets 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

1. Write a program to calculate S (n) by calculating the values of the Fibonacci sequence recursively.
2. 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).
3. 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.

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

k summing: S.

5. 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.
6. Task #7 suggests that S(n)=f (n+2)1. Prove this identity (using induction).
7. Finally, there is yet a fourth way to programmatically calculate S (n).
8. Experiment with your programs to estimate the largest n that can be computed successfully by each program.
9. 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.
10. 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 (n1)+f (n2).

Lets 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.