The Regula Falsi method - the method of the false position - for getting an approximation to a solution of an equation consists in applying the formula
with two initial guesses and . The Secant method consist in iterating the formula in a way that depends on the sign distribution of successive values of .
But there are two other (more deterministic, in a sense) ways to engage the formula in an iterative manner. To distinguish between the two I shall use different letters. One keeps one endpoint fixed:
The other replaces the endpoints at every step:
What follows constitutes a very meaningful exercise for operations with fractions. It can be carried out manually and will entertain and surprise an observant student.
We shall look for an approximation to by solving the quadratic equation . One can check that with the two iterations become
I choose and . Starting with these we get two sequences:
Now is the time for observation. What one may be expected to notice is that appears to be a subsequence of . And not just. Besides and , we also have
As a matter of fact, the indices of the terms of the -sequence which are the terms of the -sequence are
and appear to form the Fibonacci sequence. They do indeed form the Fibonacci sequence and this is worth proving.
The proof consists in verification that both sides are equal to
For all ,
The proof is by induction on . By definition,
for all . Now assume that holds for a some and all . Then, in particular, for all
as required. Which completes the proof of Proposition.
Proposition explains the manner in which sequence is embedded into sequence . Sequence converges to and so does sequence but, since skips a growing number of indices, its convergence is faster. We'll look into that in another post.
- D. Chakerian, The Rule of False Position, in Mathematical Adventures for Students and Amateurs, D. F. Hayes, T. Shubina, (editors), MAA, 2004, 157-169