# Intuition Behind a Decimal Representation with Catalan Numbers

From $0 = 0.5 - 0.5 = 0.5 - \sqrt{0.25}$, we can adjust the subtrahend slightly to obtain

$$0.5 - \sqrt{0.249} = 0.001\ 001\ 002\ 005\ 014\ 042\ldots$$

where the decimal representation contains the first few Catalan numbers: $1, 1, 2, 5, 14, 42 \ldots$

We can see even more Catalan numbers (albeit spaced apart with more $0$s) by using more $9$s.

(For example, check the decimal representation of $0.5 - \sqrt{0.24999999999}$.)

My question is not how to show this formally; it is a straightforward problem to show how one derives, e.g., the decimal representation given above. (I'll include a derivation below for anyone who doesn't want to think this through her/himself.)

Instead, my question is: why would it make sense, intuitively, for the Catalan numbers to show up in these decimal representations?

Derivation:

Recall that the generating function for the Catalan numbers $c(x)$ satisfies $c(x) = 1 + xc(x)^2$. Rearranging, we find that $c(x) = \frac{2}{1 + \sqrt{1 - 4x}}.$ Then

$$\sum_{n = 0}^{\infty}\frac{C_n}{10^{3n + 3}} = \frac{1}{1000}\sum_{n=0}^{\infty}\frac{C_n}{1000^{n}} = x \sum_{n=0}^{\infty}C_n x^n = xc(x) = \frac{2x}{1 + \sqrt{1 - 4x}},$$

where we have simplified our computations by letting $x = \frac{1}{1000}$.

Evaluating at this value of $x$ yields $0.5 - \sqrt{0.249}$.

-
I'm not sure I understand what you want intuition about. You're already aware that the Taylor series you need here is related to the generating function of the Catalan numbers. Are you asking for intuition about this? Are you familiar with how to relate the Catalan numbers to the binomial theorem with exponent $\frac{1}{2}$ and/or with how the generating function relates to various combinatorial definitions of the Catalan numbers? I guess what I'm saying is I don't understand what you don't understand about this situation. –  Qiaochu Yuan Sep 27 '12 at 8:05
I find it hard to imagine that anyone would look at $0.5 - \sqrt{0.249\ldots9}$ for the first time and expect Catalan numbers to appear in its decimal representation. Knowing they do appear, though, I wonder whether anyone can now look back and (perhaps using a specific one of the many characterizations of the Catalan numbers) say, without needing to carry out much by way of computation, "a ha, this result does not surprise me much at all, because _____." –  Benjamin Dickman Sep 27 '12 at 9:29

To make it less surprising is to fade some of the magic! But, ok.

First let us say that any real sequence $a_1,a_2,\cdots$ has an ordinary generating function (ogf) $f(x)=\sum a_ix^i$ which may be a formal series with radius of convergence $0$ (and still be useful) BUT if the $a_i$ are positive integers and $f(x)$ converges at $\frac{1}{b^k}$ then $f(\frac{1}{b^k})$ is a number whose base $b$ expansion is the sequence $a_i$ buffered by $0$'s until they start to bump into each other. I'll stick to $b=10$ and I'll use $(10^{-j})f(10^{-k})$ if there is an $a_0$ term I want to shift past the decimal point.

So the question might be which series have a nice ogf? That the Catalan numbers do is very nice.

From $\frac{1}{(1-x)^k}=\sum \binom{k+i}{k}x^i$ one obtains

$\frac{1}{0.9998}=0.10002000400080016003200640128025605121024$

$\frac{1}{10(0.999)^2}=0.10002000300040005000600070008000900100011$

$\frac{1}{10(0.999)^3}=0.10003000600100015002100280036004500550066$

Since $\binom{i}{2}+\binom{i+1}{2}=i^2$,

we can use $(\frac{1}{10}+\frac{1}{100000})\frac{1}{(1-x)^3}$ at $x=0.0001$ to get

$\frac{1.0001}{10(0.999)^3}=\frac{100010000000}{999700029999}=0.100040009001600250036004900640081010001210$

But it is more productive to use $\binom{i}{1}+2\binom{i}{2}=i^2$ for

$\frac{1}{10(1-x)^2}+\frac{1}{5000(1-x)^3}.$ Another function which coincides with the previous one at $x=0.0001.$ So the same rational but obtained another way. This second approach makes it clear how to get any polynomial sequence $a_i=p(i).$

This already seems less fun. So thinking of a dramatic last target, the Fibonacci numbers remind us that anything given by a recurrence relation (linear, with constant coefficients...) has a nice ogf.

At $x=\frac{1}{100}$,

$\frac{1}{10(1-x-x^2)}=\frac{100000}{998999}=0.1001002003005008013021034055089144$

A cute point is that all my examples (none of which are as nice as yours) lead to a rational number so as the $a_i$ increase in size and overlap they result in an eventually repeating decimal. For example the base $10$ "Fibonacci" rational I gave has period $496620$ while $\frac{10}{89}=0.\overline{11235955056179775280898876404494382022471910}$

-
The remarks on the periods are especially triggering for me, very nice! –  Gottfried Helms Sep 28 '12 at 10:19
For more on the period for examples that lead to a rational number, see the motivating article: An Unanticipated Decimal Expansion. Allen Schwenk, Math Horizons , Vol. 20, No. 1 (September 2012), pp. 10-12, jstor.org/stable/10.4169/mathhorizons.20.1.10. –  Benjamin Dickman Sep 28 '12 at 17:48

Whenever you want to invert a function you should think about Lagrange inversion. In this case you want to invert a quadratic function. Lagrange inversion happens to have an elegant proof using trees which can be found, for example, in Stanley's Enumerative Combinatorics (Vol. II). This proof interprets an implicit identity satisfied by a generating function (such as the one satisfied by the generating function for the Catalan numbers) as recursively describing a certain kind of tree; for much more on this point of view, see Bergeron, Labelle, and Leroux's Combinatorial Species and Tree-Like Structures. Specializing to this case gets you one of the flavors of trees counted by the Catalan numbers.

(But this is not the train of thought that would have actually occurred to me because the Catalan numbers are more familiar than Lagrange inversion; I just look for $\sqrt{1 - 4x}$ everywhere, and in this problem I see $\sqrt{ \frac{1}{4} - x}$, so... )

-

As a general fact, I think, intuitive is not an absolute notion. Working enough time on a mathematical subject has the effect of developping a number of authomatisms in the reasoning about that subject. This makes facts and constructions appear more intuitive, in that, we seem to acquire knowledge on them without use of reason. This phenomenon appears very clearly when you talk with an expert on a subject you do not know...

-