Let F
n be the nth Fibonacci number.
Prove that F2n+1 > F2n for all n > 1.
f(0)=0
f(1)=1
f(2)=1
f(3)=2
f(4)=3
f(5)=5
f(6)=8
f(7)=13
f(8)=21
so at the beginning of the sequence
n=2: f(3)^2 = 4, f(4)=3
n=3: f(4)^2 = 9, f(6)=8
n=4: f(5)^2 = 25, f(8)=21
Using rounding function [x]:
F(n) = [phi^n/sqrt(5)]
where phi = (1+sqrt(5))/2 the golden ratio
~= 1.618033
For n=8, this approximation is [21.0095194942485] and the portion lost in rounding gets smaller for higher values of n.
The LHS of the given inequality is multiplied by phi^2 for each successive n, while the RHS is multiplied by the same value and the inequality is maintained.
The ratio quickly approaches 1.17082039324993 (i.e., phi^2/sqrt(5)):
n LHS RHS LHS/RHS
2 4 3 1.333333333333
3 9 8 1.125000000000
4 25 21 1.190476190476
5 64 55 1.163636363636
6 169 144 1.173611111111
7 441 377 1.169761273210
8 1156 987 1.171225937183
9 3025 2584 1.170665634675
10 7921 6765 1.170879526977
11 20736 17711 1.170797809271
12 54289 46368 1.170829020014
13 142129 121393 1.170817098185
14 372100 317811 1.170821651862
15 974169 832040 1.170819912504
16 2550409 2178309 1.170820576879
17 6677056 5702887 1.170820323110
18 17480761 14930352 1.170820420041
19 45765225 39088169 1.170820383017
20 119814916 102334155 1.170820397159
21 313679521 267914296 1.170820391757
22 821223649 701408733 1.170820393820
23 2149991424 1836311903 1.170820393032
24 5628750625 4807526976 1.170820393333
25 14736260449 12586269025 1.170820393218
26 38580030724 32951280099 1.170820393262
27 101003831721 86267571272 1.170820393245
28 264431464441 225851433717 1.170820393252
29 692290561600 591286729879 1.170820393249
30 1812440220361 1548008755920 1.170820393250
31 4745030099481 4052739537881 1.170820393250
32 12422650078084 10610209857723 1.170820393250
33 32522920134769 27777890035288 1.170820393250
34 85146110326225 72723460248141 1.170820393250
35 222915410843904 190392490709135 1.170820393250
36 583600122205489 498454011879265 1.170820393250
37 1527884955772561 1304969544928660 1.170820393250
38 4000054745112196 3416454622906716 1.170820393250
Edited on May 6, 2021, 7:10 pm
|
|
Posted by Charlie
on 2021-05-06 12:42:59 |
solution
