Skip to content

Error propagation in a Fibonacci calculation

Question

You compute Fibonacci numbers F0,…,F99F_0,\dots,F_{99} correctly but record F100F_{100} as G100=F100+1G_{100}=F_{100}+1. You then keep applying the recurrence to your recorded values to obtain G101,…,G110G_{101},\dots,G_{110}. What is G110−F110G_{110}-F_{110}?

Short answer

89. The error en=Gn−Fne_n=G_n-F_n obeys the same recurrence, with e99=0e_{99}=0 and e100=1e_{100}=1. So en=Fn−99e_n=F_{n-99}, and e110=F11=89e_{110}=F_{11}=89.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free