Infinite fraction

Question

I wasn't sure if this belongs to programming but the problems seems more mathematical so i posted here.

I was looking at pi and made a function(Haskell) similar to it without squaring

fx a b = if a == 0 then 1 else ( 4 + (b / fx (a-1) (b + 2 )))

The job of this function is only to control recursion to give an value for the infinite function up to a certain recursive step. However after certain value like a = 70 and b = 7 number will always be this no matter how high is a

5.261723603946203

What I don't understand is how did a infinite fraction like this have a constant value.

Function is based on https://en.wikipedia.org/wiki/Pi

EDIT 1

It was probably a precision problem

Prelude> 0.999999999999999999
1.0

Answer 1

I think @jdods point of understanding convergence and continued fractions is relevant.

Here is some ideas that might help point you in the right direction:

At first, I'm not going to look at your example, but at a famous one. The golden ratio can be written as a continued fraction. But first we represent it recursively

Prelude> let f n = if n == 0 then 1 else ( 1 + 1 / f (n-1) )
Prelude> f 10
1.6179775280898876
Prelude> f 100
1.618033988749895
Prelude> f 10000
1.618033988749895

Note that is approximately $\phi = \frac{1+\sqrt{5}}{2}$, and as n get's bigger it becomes a closer approximation. It actually is precise in some sense at n = 100, computers are finite, and Floats have limited precision:

Prelude> (1 + sqrt 5) / 2
1.618033988749895

Observation: if you unroll the recursion you get the infinite fraction $$\phi = 1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cdots}}}$$ you some how get a value that is finite. Why? We are curious of what value f n becomes as n gets large and if it will get closer and closer to some constant (a "limit"). A function like g n = (-1) ^ n doesn't work, it wobbles around. So how do we know f n has a limit?

An interesting mathematical fact found here is a sufficient criterion for when a continued fraction converges to a limit. We can write generic continued fraction $A$ as $$A = a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cdots}}}$$ that can be thought as a bunch of partial steps $$A_0 = a_0$$ $$A_1 = a_0+\frac{1}{a_1}$$ $$A_2 = a_0+\cfrac{1}{a_1+\frac{1}{a_2}}$$ The theorem say that $A_n$ eventually approach a constant value if each of the $a_i$s are positive integers.

This confirms the case with $\phi$, we're not there in our case. But at this point we know continued fractions can converge, and sometimes we can can show this by applying theorems.

Let's look at another intermediate problem which I'll call fx2. As you can see it is your case with some of the constants set to 1.

Prelude> let fx2 a b = if a == 0 then 1 else ( 1 + (b / fx (a-1) (b+1)))
Prelude> fx2 10 10
2.7111266944665005
Prelude> fx2 1000 10
2.711545039663546
Prelude> fx2 10 13
3.0915580685545767
Prelude> fx2 1000 13
3.092654214082659
Prelude> fx2 100000 13
3.092654214082659

Note it has similar properties to fx. When you fix b and try larger and larger a, it converges. Let look what happens when $b = 1$ (see NOTE below for other values) $$A = 1+\cfrac{1}{1+\cfrac{2}{1+\cfrac{3}{1+\cfrac{4}{1+\cdots}}}}$$ Using algebra, we can turn this into a continued fraction $$A = 1+\cfrac{1}{1+\cfrac{1}{\frac{1}{2}+\cfrac{1}{\frac{2}{3}+\cfrac{1}{\frac{3}{8}+\cdots}}}}$$ A continued fraction where if we define $a_i$ in $$A = a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cdots}}}$$ by $$a_k = \frac{(k-1) \times (k-3) \times (k-5) \times \ldots \times 2}{k \times (k-2) \times (k-4) \times (k-6) \times \ldots \times 1}$$ if $k$ is odd and $$a_k = \frac{(k-1) \times (k-3) \times (k-5) \times \ldots \times 1}{k \times (k-2) \times (k-4) \times (k-6) \times \ldots \times 2}$$ if $k$ is even. Does this converge? The $a_k$s are not positive integers, so the theorem above used for the golden ratio doesn't apply. But, there is another theorem in that source that says if $\sum_k a_k$ becomes infinite then the continued fraction converges. I expect this will work here, but I have not done it.

NOTE: that before we set b=1, this is general enough because if for example b=3, and the expression $$A' = 1+\cfrac{3}{1+\cfrac{4}{1+\cfrac{5}{1+\cfrac{6}{1+\cdots}}}}$$ didn't converge then neither would $$A = 1+\cfrac{1}{1+\cfrac{2}{1+\cfrac{3}{1+\cfrac{4}{1+\cdots}}}}$$

I'm a bit burned out (might edit this later) to show fx converges. But here is a rough "recipe" I expect will work.

1. Unroll your recursion and, using algebra, try to represent it as a continued fraction with a formula for $a_i$.
2. Show that $\sum_i a_i$ is infinite.

Both these steps will take some work.

Edit: If someone wants to flesh out the divergence proof above $$a_{2k} = \frac{(2k-1) \times (2k-3) \times (2k-5) \times \ldots \times 1}{k \times (2k-2) \times (2k-4) \times (2k-6) \times \ldots \times 2} = \frac{(2k)!}{4^k k!^2}$$ The central binomial coefficient is asymptotically $\binom{2k}{k} \sim \frac{4^k}{\sqrt{\pi n}}$ so $\frac{2k!}{4^k k!^2} = \frac{1}{4^k}\binom{2k}{k} \sim \frac{1}{\sqrt{\pi n}}$ and the sums of $a_{2k}$ will diverge will be grow faster than the harmonic sum. However this depends on even more mathematical knowledge that I don't think that will help the reader in this case.