Fibonacci

What is the upper and lower bound of Fibonacci series when we use int variables?

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 (from wiki)

I would code the Fibonacci series as follows.

fib(n)
x = -1, y = 1 
for n times: 
  z = x+y
  print z
  x = y, y = z

The issue is that x is not unsigned and you miss the 32nd bit i.e. I cannot print above 2^31-1.

Coming back to the bounds.

fib(n>1) = fib(n-1) + fib(n-2)
fib(n=0) = 0, fib(n=1) = 1

An approximation for the lower bound:
fiblower(n) = 2 * f(n-1)
For n=32, we get 2^32 *f(1). Lower bound for n is 32.

By some observation you can see that for the upper bound:
fibupper(n) = 3/2 * f(n-1)
For n=64 (with little calculation), we get above 2^32. Upper bound for n is 64.

Anyways, the ratio of the Fibonacci numbers tend to the golden ratio Φ (Φ = 1.6180339887...).
i.e. f(n) ~ Φ * f(n-1)

[Hat tip to AN]