Description
You are familiar with the Fibonacci sequence from various places
Equ 1
f (1)=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
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
g(n)=(
1
√5 )(
1+√5
2 )
n
−(
1
√5 )(
1−√5
2 )
n
.
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
summing: S (n)=∑
k=0
n
(
1
√5 )(
1+√5
2 )
k
−(
1
√5)(
1−√5
2 )
k
.
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?