I wanted to write a proof similar to the one on page $3$ here ($2.2$ Fibonacci numbers):
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf ,
to show that a sequence, defined with recurrence, grows exponentially. But I have some questions about this proof (also I kind of understand the idea but I don't known exactly what is the theory behind it..)
First (maybe this is just notation): It says "..the other root of the quadratic equation has smaller absolute value, so we can ignore it.." and write:
\begin{equation} F_n \leq \alpha \phi^n \end{equation} but it would not be possible to write it like that if $\phi$ was a complex number with imaginary part, Would it be then $F_n \leq \alpha |\phi|^n$?
Second: I don't get the fact that it is sufficient to use the base case (with an "$=$" sign?) to choose $\alpha$, it is not clear for me why it will then work with the third value for example.. or is that because we don't care for small $n$?
Thanks a lot!
It says "..the other root of the quadratic equation has smaller absolute value, so we can ignore it.." and write: Fn≤αϕn but it would not be possible to write it like that if ϕ was a complex number with imaginary part, Would it be then Fn≤α|ϕ|n?
The roots of $c^2-c-1$ are both real numbers, $c_1 = -0,61803399$ and $c_2 = 1,61803399$.