Continued Fractions - The Journey to Infinity

From time immemorial, the infinite has stirred men's emotions more than any other question. Hardly any other idea has stimulated the mind so fruitfully ... In a certain sense, mathematical analysis is a symphony of the infinite. - David Hilbert

Hello everyone!

Today I am going to briefly discuss about infinite continued fraction. I am very new to this branch of mathematics. So I shall be glad to accept suggestions from readers to improve this article.

A continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number,  General form of an infinite continued fraction is $$a_{0}+{\cfrac {b_{1}}{a_{1}+{\cfrac {b_{2}}{a_{2}+{\cfrac {b_{3}}{a_{3}+{_{\ddots }}}}}}}}=a_{0}+{1 \over a_{1}+{}}{1 \over a_{2}+{}}{1 \over a_{3}+{}\cdots}$$ where $a_i$ and $b_i$ are either rational numbers, real numbers, or complex numbers.

Any whole number can be expressed as an infinite continued fraction. We shall try to find the infinite continued fraction representation of a natural number $n$. Let $a=n^2-n$. Then the equation $x^2-x-a=0$ has a solution $x=n$. Rearranging the equation, $x=1+a/x$. We keep on substituting $x$ on the right-hand side by $1+a/x$ and get the infinite continued fraction $$1+{\cfrac {a}{1+{\cfrac {a}{1+{\cfrac {a}{1+{_{\ddots }}}}}}}}$$

We can get a beautiful infinite continued fraction representation of famous '' Golden Ratio". We know that golden ratio ($\phi$) satisfy the equation $x^2-x-1=0$. So $x=1+1/x$. Using similar method, we get $$\phi = 1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+{_{\ddots }}}}}}}}$$

Square-root of natural numbers also have continued fraction representation. $$\sqrt{x}=1+\sqrt{x}-1$$ $$=1+\frac{x-1}{\sqrt{x}-1}$$ Substituting $x$ on the right-hand side repetitively we get $$\sqrt{x}=1+{\cfrac {x-1}{2+{\cfrac {x-1}{2+{\cfrac {x-1}{2+{_{\ddots }}}}}}}}$$

Now I am going to derive a well-known identity between series and continued fraction from which we can derive many beautiful results.

Let $a_1$, $a_2$, $a_3$, ... be any real numbers with $a_k\neq 0$ and $a_k\neq a_{k-1}$ for all $k$. $$\frac{1}{a_1}-\frac{1}{a_2}=\frac{a_2-a_1}{a_1a_2}$$ $$=\frac{a_2-a_1}{a_1(a_2-a_1)+a_1^2}$$ $$=\cfrac{1}{a_1 + \cfrac{a_1^2}{a_2-a_1}}$$

Proceeding similarly we get the following identity, $$\sum_{k=1}^{n}\frac{(-1)^{k-1}}{a_k}= \cfrac{1}{a_1 + \cfrac{a_1^2}{a_2-a_1 + \cfrac{a_2^2}{a_3-a_2 + \cfrac{\ddots}{a_{n-1}+\cfrac{a_{n-1}^2}{a_n-a_{n-1}}}}}}$$

Taking $n \to \infty$, we get our final result  $$\sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{a_k}= {1 \over a_{1}+{}}{a_1^2 \over a_{2}-a_{1}+{}}{a_2^2 \over a_{3}-a_{2}+{}\cdots}$$

Now we are in a position to derive some identities using above relation which at first glance seems almost like magic. :)

Taylor series expansion of $\tan^{-1}x$ is given by $$\tan^{-1}x=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}-\cdots$$

Substituting $x=1$ we get $$\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\cdots$$

Using the series-continued fraction identity we get the astounding result $$\frac{\pi}{4}={\cfrac {1}{1+{\cfrac {1^2}{2+{\cfrac {3^2}{2+{\cfrac {5^2}{2+{\cfrac {7^2}{2+{_{\ddots }}}}}}}}}}}}$$

Inverting it we get the identity given by Lord Brouncker $$\frac{4}{\pi}=1+{\cfrac {1^2}{2+{\cfrac {3^2}{2+{\cfrac {5^2}{2+{\cfrac {7^2}{2+{_{\ddots }}}}}}}}}}$$
There is another interesting identity involving series and continued fraction. Let $a_1$. $a_2$, $a_3$, ... be real, nonzero, and never equal to $1$. Then, $$\frac{1}{a_1}-\frac{1}{a_1a_2}=\frac{a_2-1}{a_1a_2}$$ $$=\frac{a_2-1}{a_1(a_2-1)+a_1}$$ $$=\cfrac{1}{a_1 + \cfrac{a_1}{a_2-1}}$$
We can continue doing similar process and get the identity $$\sum_{k=1}^{n}\frac{(-1)^{k-1}}{a_1 \cdots a_k}=\cfrac{1}{a_1 + \cfrac{a_1}{a_2-1 + \cfrac{a_2}{a_3-1 + \cfrac{\ddots}{a_{n-1}+\cfrac{a_{n-1}}{a_n-1}}}}}$$
Taking $n \to \infty$ $$\sum_{k=1}^{n}\frac{(-1)^{k-1}}{a_1 \cdots a_k}= {1 \over a_{1}+{}}{a_1 \over a_{2}-1+{}}{a_2 \over a_{3}-1+{}\cdots}$$
We use this identity to find the infinite continued fraction representation of another famous transcendental number $e$.
$$\frac{e-1}{e}=1-\sum_{n=0}^{\infty}\frac{(-1)^n}{n!}=1-\frac{1}{1}+\frac{1}{1\cdot 2}-\frac{1}{1 \cdot 2 \cdot 3}+\cdots$$
So $$\frac{e-1}{e}={\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {2}{2+{\cfrac {3}{3+\ddots }}}}}}}}$$
Inverting and subtracting $1$ from both sides, we get $$\frac{1}{e-1}={\cfrac {1}{1+{\cfrac {2}{2+{\cfrac {3}{3+\ddots }}}}}}$$
Inverting again and adding $1$ to both sides, finally we get $$e=2+{\cfrac {2}{2+{\cfrac {3}{3+{\cfrac {4}{4+{\cfrac {5}{5+{_{\ddots }}}}}}}}}}$$
The canonical continued fraction representation of $e$ also has a very regular structure. I shall try to cover that in my next post. It is really amazing how two most important transcendental numbers ($\pi$ and $e$) have highly regular infinite continued fraction representations.

Thanks for reading :)

Partition Function and Waring's Problem

Hello everyone! In this post I shall briefly discuss about the partition function.

A partition of a number $n$ is a representation of $n$ as the sum of any number of positive integral parts. $p(n)$ is the number of partitions of $n$. For example $p(5)=7$ as

$5=5$
   $=4+1$
   $=3+2$
   $=3+1+1$
   $=2+2+1$
   $=2+1+1+1$
   $=1+1+1+1+1$

Generating function of $p(n)$ is given by $$1+\sum _{n=1}^{\infty }p(n)x^n=\prod _{k=1}^{\infty }{\frac {1}{1-x^k}}$$
We can rewrite the infinite product as $$(1+x+x^2+...)$$ $$(1+x^2+x^4+...)$$ $$(1+x^3+x^6+...)$$ $$\dots$$
and multiplying the series. Every partition of $n$ contributes $1$ to the coefficient of $x^n$.

From Pentagonal Number Theorem, $$\prod _{{n=1}}^{{\infty }}\left(1-x^{{n}}\right)=1+\sum _{{k=1}}^{\infty }(-1)^{k}\left(x^{{k(3k+1)/2}}+x^{{k(3k-1)/2}}\right)$$
We can derive a recurrence relation of $p(n)$ using above identity.
$$p(n)=\sum_{k=1}^{n}(-1)^{k+1}\left[p\left(n-\frac{1}{2}k(3k-1)\right)+p\left(n-\frac{1}{2}k(3k+1)\right)\right]$$
Using this recurrence we can write a program to calculate $p(n)$ in $O(n^{3/2})$ time.

import java.io.*;
import java.util.*;
import java.math.*;

public class Partition {

    public static int N = 200;
    public static BigInteger[] p = new BigInteger[N + 1];
    public static int[] x = new int[10001]; // i * (3 * i - 1) / 2
    public static int[] y = new int[10001]; // -i * (-3 * i - 1) / 2

    public static void main(String[] args) {
        double start = System.currentTimeMillis();
        int ax = 1;
        for (int i = 1; i <= 10000; i++) {
            x[i] = x[i - 1] + ax;
            y[i] = y[i - 1] + ax + 1;
            ax += 3;
        }
        p[0] = BigInteger.valueOf(1);
        p[1] = BigInteger.valueOf(1);
        for (int i = 2; i <= N; i++) {
            p[i] = BigInteger.valueOf(0);
            for (int j = 1; ; j++) {
                if (x[j] > i && y[j] > i) {
                    break;
                }
                if (j % 2 == 1) {
                    if (x[j] <= i) p[i] = p[i].add(p[i - x[j]]);
                    if (y[j] <= i) p[i] = p[i].add(p[i - y[j]]);
                } else {
                    if (x[j] <= i) p[i] = p[i].subtract(p[i - x[j]]);
                    if (y[j] <= i) p[i] = p[i].subtract(p[i - y[j]]);
                }
            }
        }
        System.out.println("P(" + N + ") = " + p[N]);
        double end = System.currentTimeMillis();
        System.out.println("Time elapsed : " + ((end - start) / 1000d) + " seconds");
    }
}

Ramanujan and G. H. Hardy derived an asymptotic formula of $p(n)$. Its derivation is beyond the scope of this article.
$${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)} \hspace{5 mm} \text{as} \hspace{5 mm} {\displaystyle n\rightarrow \infty }$$

Waring's problem is the generalization of partition function. Waring's problem asks whether it is possible to represent positive integers as sums of a fixed number $s$ of non-negative $k$-th powers.
$$n=x_1^k+x_2^k+x_3^k+ \dots + x_s^k$$ $g(k)$ is defined as the least value of $s$ such that above equation is solvable for all $n$. $G(k)$ is defined as the least value of $s$ for which above holds true for sufficiently large numbers, i.e. all numbers with at most a finite number of exceptions. So $G(k) \le g(k)$.

Let $q=\left[\left(\frac{3}{2}\right)^k\right]$. The number $n=2^kq-1 < 3^k$ can be represented by only the powers $1^k$ and $2^k$. $$n=(q-1)2^k+(2^k-1)1^k$$ So $$g(k) \geq 2^{k}+[(3/2)^{k}]-2$$
Interested reader can find detailed discussion here.

Thaks for reading :)