Intuition Behind a Decimal Representation with Catalan Numbers

Question

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}$.

Answer 1

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}{10\cdot 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}$

Answer 2

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... )

Answer 3

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...