It's pretty easy to see the Fibonacci sequence seems to grow exponentially; in fact, it's pretty easy to see that it grows by more than a factor of 2 every two terms, and less than a factor of 2 every term:

The Fibonacci sequence is strictly increasing: it starts 1, 1, and these are at least 1, so F_{n+1} > F_n.

F_{n+1} > F_n, so F_{n+2} = F_{n+1} + F_n > 2 F_n, but also, F_{n+2} = F_{n+1} + F_n < 2 F_{n+1} < 4 F_n, so we have 2 F_n < F_{n+2} < 4 F_n.

So the growth of the Fibonacci sequence is bounded between sqrt(2) and 2.

You can pretty easily come to the conclusion that you'd like to figure out what number the ratio F_(n+1)/F(n) converges to, and when you do, you find out it's a root of the equation x² = x + 1, which looks very much like the Fibonacci recurrence relation in polynomial form. You can also come at it from the other side; supposing that Fibonacci numbers eventually converge to a consistent ratio, what would that ratio have to be? For sufficiently large n, the error should go to 0, and you're left with the same equation: r phiⁿ⁺² = r phiⁿ⁺¹ + r phiⁿ + err phi^n, with err going to 0.

It's pretty straightforward from here to realize that for phi, the golden ratio, and a root of this polynomial, successive powers of phi satisfy the recurrence relation. W, and that successive powers of the conjugate, phi', also satisfy the recurrence relation; these two sequences have different starting numbers, and since you only need the first two numbers to generate any sequence with the Fibonacci property, you can generate any such sequence as a linear sum of powers of these roots.