Description
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?
