|
$F_n = F_{n-1} + F_{n-2}$ $F_n > F_{n-1}$ $F_{n-1} > F_{n-2}$ $=>$ Start with $F_n = F_{n-1} + F_{n-2}$, and make the right side bigger by replacing $F_{n-2}$ with $F_{n-1}$ $F_n < F_{n-1} + F_{n-1}$ $=>$ $F_n < 2F_{n-1}$ $=>$ $F_n < 2^n$ So the fibonacci sequence, one item at a time, grows more slowly than $2^n$. But on the other hand every 2 items the Fibonacci sequence more than doubles itself: $(1) F_n = F_{n-1} + F_{n-2}$ $(2) F_{n-1} = F_{n-2} + F_{n-3}$ $=>$ Replace $F_{n-1}$ in $(1)$ with $F_{n-1}$ from $(2)$ $F_n = 2F_{n-2} + F_{n-3}$ $=>$ Because $F_{n-3}$ is greater than zero, we can drop it from the right side, and that makes the right side smaller than the left. $F_n > 2F_{n-2}$ $=>$ $F_n > 2^{n/2}$ $F_n > (2^{1/2})^n$ $F_n > \sqrt{2}^n$ Because the Fibonacci sequence is bounded between two exponential functions, it's effectively an exponential function with the base somewhere between 1.41 and 2. ${1.41}^n$ < $F_n < 2^n$ That base ends up being the golden ratio. See https://math.stackexchange.com/a/1201069/62698 (责任编辑:) |
