# Proof

(related to Algorithm: Continued Fraction (Python))

### Proof of correctness

• In the first step, the floor (integer part) $q_0:=\lfloor x\rfloor$ of $x$ is extracted and appended to the list $\mathtt{cf}.$
• After the step $x_0:=x-q_0,$ the number $x_0$ fulfills $0\le x_0 < 1$ and contains the fractional part of the original $x$ value.
• In the $\mathtt{while}$ loop, we have $q_{i+1}=\left\lfloor\frac{1}{x_i}\right\rfloor$, $x_{i+1}=\frac{1}{x_i}-q_{i+1}=\frac{1}{x_i}-\left\lfloor\frac{1}{x_i}\right\rfloor.$
• On the other hand, we have in each step $$x_i=\frac{1}{q_{i+1}+x_{i+1}}=\frac{1}{\left\lfloor\frac{1}{x_i}\right\rfloor+\frac{1}{x_i}-\left\lfloor\frac{1}{x_i}\right\rfloor}.$$
• By iteration, we get $$x=\lfloor x\rfloor + \frac{1}{q_1+x_1}=\lfloor x\rfloor + \frac{1}{q_1+\frac{1}{q_2+x_2}}=\ldots$$
• By the definition of the continued fractions, this means $$x=[x_0;q_1+x_1]=[x_0;q_1,q_2+x_1]=\ldots=[x_0;q_1,\ldots,q_{i-1},q_i+x_i].$$

Github: ### References

#### Bibliography

1. Hermann, D.: "Algorithmen Arbeitsbuch", Addison-Wesley Publishing Company, 1992
2. Schnorr, C.P.: "Lecture Notes Diskrete Mathematik", Goethe University Frankfurt, 2001