# Recurrence relation with python. [closed]

How to find the terminating value of the continued fractions $$S=3-\cfrac2{3-\cfrac2{3-\cfrac2{\ddots}}}$$ by writing a recurrence relation in Python? (Start from any guess value other than 1.)

• Why don't you write the recurrence relation on paper first? – copper.hat Apr 1 '20 at 20:11
• $S=3-\dfrac2S\implies S^2-3S+2=0\iff S=1$ or $2$ – J. W. Tanner Apr 1 '20 at 20:12
• Yours is a good question that is receiving close votes. I think that's because you haven't given enough information of the context of your question and what your thoughts about it are. – Rob Arthan Apr 1 '20 at 21:07

## 3 Answers

Write your equation as $$S=3-\frac{2}S$$ Notice that $$S=1$$ is a solution, however I think it's unstable. Then just start with any number $$S_0$$ not equal to $$1$$. Then repeat $$S_{n}=3-\frac2{S_{n-1}}$$ until $$|S_n-S_{n-1}|<\varepsilon$$.

Additional: Following the comment from @RobArthan, let's see what's happening if you are close to either of the two solutions $$S=1$$ or $$S=2$$.

Let's choose $$S_n=1+\alpha$$, where $$|\alpha|\ll1$$. Then $$S_{n+1}-1=3-\frac 2{1+\alpha}-1=\frac{2\alpha}{1+\alpha}\approx2\alpha$$

So starting from any point in the vicinity of $$1$$ the next iteration will be further away (about a factor of $$2$$ further than the initial condition).

How about $$2$$? We repeat the same steps: $$S_n=2+\alpha$$ $$S_{n+1}-2=3-\frac{2}{2+\alpha}-2=\frac{\alpha}{2+\alpha}\approx\frac\alpha2$$ So starting close to $$2$$, in the next step you are getting twice as close as before. Therefore $$2$$ is a stable solution

• I have numerical evidence supporting your suggestion that the solution at $S = 1$ is unstable. I'd be interested to understand why. – Rob Arthan Apr 1 '20 at 22:03
• @RobArthan I've added a discussion of the stability of the solutions – Andrei Apr 1 '20 at 22:47

For a suitable function $$f$$, we can iterate an estimate $$S$$ to $$f(S)$$ with a for loop, terminated either when the change in $$S$$ is small or after a large number of iterations. Fewer iterations are needed if $$f$$ is Newton-Raphson inspired than if you just use $$f(S):=3-2/S$$. In particular, $$S=3-2/S\implies S^2-3S+2=0$$, so you could choose $$f(S)=S-\frac{S^2-3S+2}{2S-3}=\frac{S^2-2}{2S-3}$$.

Of course, there's no need to iterate anyway, as clearly $$S=3-2/S\implies S\in\{1,\,2\}$$. Mathematically, there are two interesting questions: which value of $$S$$ if either is mandated by the definition of $$S$$ (is it even well-defined?), and which choice of $$f$$ gives stable convergence to such a value from a wide range of nearby estimates of $$S$$?

We must define $$S$$ as the limit of a sequence. The obvious choice is $$S_0:=3,\,S_{n+1}:=3-\frac{2}{S_n}$$. You can easily prove by induction that $$S_n\in(2,\,3]$$, so $$S=2$$; $$S\ne1$$. However, you'll find an estimate close to either $$1$$ or $$2$$ leads to stable behaviour with the above Newton-Raphson choice of iteration. (This can be proven by considering the first few derivatives of $$f$$.)

We can easily show that your continued fraction is equal to $$1$$ or $$2$$. In fact: $$S=3-\dfrac2S\implies S^2-3S+2=0\iff S=1$$

Here I will post a very useful algorithm that I always use when I have to operate with continued fraction:

from decimal import Decimal
from fractions import Fraction

class CFraction(list):

def __init__(self, value, maxterms=15, cutoff=1e-10):
if isinstance(value, (int, float, Decimal)):
value = Decimal(value)
remainder = int(value)
self.append(remainder)

while len(self) < maxterms:
value -= remainder
if value > cutoff:
value = Decimal(1) / value
remainder = int(value)
self.append(remainder)
else:
break
elif isinstance(value, (list, tuple)):
self.extend(value)
else:
raise ValueError("CFraction requires number or list")

def fraction(self, terms=None):
"Convert to a Fraction."

if terms is None or terms >= len(self):
terms = len(self) - 1

frac = Fraction(1, self[terms])
for t in reversed(self[1:terms]):
frac = 1 / (frac + t)

frac += self
return frac

def __float__(self):
return float(self.fraction())

def __str__(self):
return "[%s]" % ", ".join([str(x) for x in self])

if __name__ == "__main__":
from math import e, pi, sqrt

numbers = {
"phi": (1 + sqrt(5)) / 2,
"pi": pi,
"e": e,
}

print "Continued fractions of well-known numbers"
for name, value in numbers.items():
print "   %-8s  %r" % (name, CFraction(value))

for name, value in numbers.items():
print
print "Approximations to", name
cf = CFraction(value)
for t in xrange(len(cf)):
print "   ", cf.fraction(t)

print
print "Some irrational square roots"
for n in 2, 3, 5, 6, 7, 8:
print "   ", "sqrt(%d)  %r" % (n, CFraction(sqrt(n)))

print
print "Decimals from 0.1 to 0.9"
for n in xrange(1, 10):
cf = CFraction(n / 10.0)
print "   ", float(cf), cf


As you can note, it can be used to print the continued fraction for all the square roots, irrational number and also general continued fraction as yours.

• But the quadratic $S^2 -3S +2$ has two roots; $1$ and $2$. – Rob Arthan Apr 1 '20 at 21:12
• @Rob Arthab: yes, sorry. My error. – Matteo Apr 1 '20 at 21:17
• @Matteo can you run the code with this equation? – Shubhadeep Roy Apr 2 '20 at 5:13