How to find next fibonacci number if given a fibonacci number?

How to find next fibonacci number if given a fibonacci number?

for eg if n = 8

it’s answer should be 13.

1 Like

What is the required time complexity?

O(1) Time Complexity.

What is the range of n?

Range of n ?

Btw, did you go through this? Trust me, I didn’t extract it from the deep web, just a simple Google search. :slightly_smiling_face:


this is the correct way but i remember it’s not accurate for very large value of n’s
(which is why you asked for the range of n right?)


I think this formula is the best.
Proof is also given.

but it only works for smaller values. maximum upto 50

Who told you that. I think it will work for every value.

go through that page and read the comments.

This is the plot of the absolute errors of the values approximated by the formula for values of X \in [1, 82]. The max value of the range is denoted by MAX in the Python 3 script. You may play with them to see how the values change.

Here's the code
from math import sqrt
from matplotlib import pyplot as plt

MAX = 82 # limit of X
num = (1 + sqrt(5)) / 2 # multiplying factor

# creating the lists
X		= [_ for _ in range(1, MAX + 1)]	# index
Fib		= [1 for _ in range(1, MAX + 1)]	# Actual values
Approx	= [1 for _ in range(1, MAX + 1)]	# Approx values
Err		= [1 for _ in range(1, MAX + 1)]	# |Real - Approx|

# fill 'em up
for _ in range(2, MAX):
	Fib[_] = Fib[_ - 1] + Fib[_ - 2]
for _ in range(1, MAX):
	Approx[_] = int(Fib[_ - 1] * num)
for _ in range(1, MAX):
	Err[_] = abs(Fib[_] - Approx[_])

# X vs Error

# values
for _ in range(0, MAX):
	print("%d\t%d" % (X[_], Err[_]))

# plot
plt.plot(X, Err, color = 'r')