# CTK Insights

• ## Pages

19 Apr

### The Regula Falsi - Iterated

The Regula Falsi method - the method of the false position - for getting an approximation to a solution of an equation $f(x)=0$ consists in applying the formula

$t=\frac{x_{1}f(x_{2})-x_{2}f(x_{1})}{f(x_{2})-(f(x_{1})}$

with two initial guesses $x_{1}$ and $x_{2}$. The Secant method consist in iterating the formula in a way that depends on the sign distribution of successive values of $f(x)$.

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:

$a_{n+1}=\frac{a_{1}f(a_{n})-a_{n}f(a_{1})}{f(a_{n})-(f(a_{1})}$.

The other replaces the endpoints at every step:

$b_{n+1}=\frac{b_{n-1}f(b_{n})-b_{n}f(b_{n-1})}{f(b_{n})-(f(b_{n-1})}$.

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 $\sqrt{2}$ by solving the quadratic equation $x^{2}-2=0$. One can check that with $f(x)=x^{2}-2$ the two iterations become

$a_{n+1}=\frac{a_{1}a_{n}+2}{a_{n}+a_{1}}$.

and, respectively,

$b_{n+1}=\frac{b_{n-1}b_{n}+2}{b_{n}+b_{n-1}}$.

I choose $a_{1}=b_{1}=1$ and $a_{2}=b_{2}=3/2$. Starting with these we get two sequences:

$a_{n}=\{1,3/2,7/5,17/12,41/29,99/70,239/169,577/408,\ldots\}$

and

$b_{n}=\{1,3/2,7/5,41/29,577/408,47321/33461\ldots\}$

Now is the time for observation. What one may be expected to notice is that $b_{n}$ appears to be a subsequence of $a_{n}$. And not just. Besides $b_{1}=a_{1}$ and $b_{2}=a_{2}$, we also have

$b_{3}=a_{3},b_{4}=a_{5},b_{5}=a_{8},\ldots$

As a matter of fact, the indices of the terms of the $a$-sequence which are the terms of the $b$-sequence are

$1, 2, 3, 5, 8,\ldots$

and appear to form the Fibonacci sequence. They do indeed form the Fibonacci sequence and this is worth proving.

Define $F(x,y)=\frac{xy+2}{x+y}$. So defined function $F$ has the properties of commutativity $F(x.y)=F(y,x)$ and associativity:

$F(x,F(y,z))=F(F(x,y),z)$.

The proof consists in verification that both sides are equal to

$\frac{xyz + 2(x+y+z)}{xy+yz+zx+2}$.

### Proposition

For all $m, n\gt 0$,

$a_{m+n}=F(a_{m},a_{n})=\frac{a_{m}a_{n}+2}{a_{m}+a_{n}}$.

### Proof

The proof is by induction on $m$. By definition,

$a_{1+n}=F(a_{1},a_{n})=\frac{a_{1}a_{n}+2}{a_{1}+a_{n}}$,

for all $n\gt 0$. Now assume that $a_{m+n}=F(a_{m},a_{n})$ holds for a some $m=k\gt 0$ and all $n\gt 0$. Then, in particular, for all $n$

$a_{k+(n+1)}=F(a_{k},a_{n+1})=F(a_{k},F(a_{1},a_{n}))=F(F(a_{k},a_{1}),a_{n})=F(a_{k+1},a_{n})$,

implying

$a_{(k+1)+n}=a_{k+(n+1)}=F(a_{k+1},a_{n})$,

as required. Which completes the proof of Proposition.

Proposition explains the manner in which sequence $b_{n}$ is embedded into sequence $a_{n}$. Sequence $a_{n}$ converges to $\sqrt{2}$ and so does sequence $b_{n}$ but, since $b_{n}$ skips a growing number of indices, its convergence is faster. We'll look into that in another post.

### References

1. D. Chakerian, The Rule of False Position, in Mathematical Adventures for Students and Amateurs, D. F. Hayes, T. Shubina, (editors), MAA, 2004, 157-169