Generate 50 Fibonacci numbers
We can do this two ways:
1) Recursive Algorithm
2) Binet's Formula
Recursive Algorithm:
Fn = Fn - 1 + Fn - 2
where F0 = 0 and F1 = 1
Show Fibonacci Formula:
N/A + 0
N/A + 1
1 + 0 + 1
1 + 1 + 2
2 + 1 + 3
3 + 2 + 5
5 + 3 + 8
8 + 5 + 13
13 + 8 + 21
21 + 13 + 34
34 + 21 + 55
55 + 34 + 89
89 + 55 + 144
144 + 89 + 233
233 + 144 + 377
377 + 233 + 610
610 + 377 + 987
987 + 610 + 1,597
1,597 + 987 + 2,584
2,584 + 1,597 + 4,181
4,181 + 2,584 + 6,765
6,765 + 4,181 + 10,946
10,946 + 6,765 + 17,711
17,711 + 10,946 + 28,657
28,657 + 17,711 + 46,368
46,368 + 28,657 + 75,025
75,025 + 46,368 + 121,393
121,393 + 75,025 + 196,418
196,418 + 121,393 + 317,811
317,811 + 196,418 + 514,229
514,229 + 317,811 + 832,040
832,040 + 514,229 + 1,346,269
1,346,269 + 832,040 + 2,178,309
2,178,309 + 1,346,269 + 3,524,578
3,524,578 + 2,178,309 + 5,702,887
5,702,887 + 3,524,578 + 9,227,465
9,227,465 + 5,702,887 + 14,930,352
14,930,352 + 9,227,465 + 24,157,817
24,157,817 + 14,930,352 + 39,088,169
39,088,169 + 24,157,817 + 63,245,986
63,245,986 + 39,088,169 + 102,334,155
102,334,155 + 63,245,986 + 165,580,141
165,580,141 + 102,334,155 + 267,914,296
267,914,296 + 165,580,141 + 433,494,437
433,494,437 + 267,914,296 + 701,408,733
701,408,733 + 433,494,437 + 1,134,903,170
1,134,903,170 + 701,408,733 + 1,836,311,903
1,836,311,903 + 1,134,903,170 + 2,971,215,073
2,971,215,073 + 1,836,311,903 + 4,807,526,976
4,807,526,976 + 2,971,215,073 + 7,778,742,049
Use Binet's Formula
Fn = 1/√5(((1 + √5)/2)n - ((1 - √5)/2)n)
Given n = 49, we have:
F49 = 0.44721359549996 * ((3.2360679774998/2)49 - (-1.2360679774998/2)49)
F49 = 0.44721359549996 * ((1.6180339887499)49 - (-0.61803398874989)49)
F49 = 0.44721359549996 * (17393796001 - -5.7491763151788E-11)
F49 = 0.44721359549996 * 17393796001
