Is this a coincidence too?

Number Theory Level 4

If we write out the decimal expansion of the smaller root of $f(x)=1000000x^2-1000000x+1$ , we get the following decimal: $0.000001 \quad 000001\quad 000002\quad 000005 \quad 000014 \quad \ldots$ which we notice as the first 5 Catalan numbers. How many distinct Catalan numbers occur in a row before this pattern stops?

Image Credit: Wikimedia Dmharvey .

The answer is 12.

2 solutions

Michael Mendrin
Jun 29, 2015

We first start with a generating function with Catalan number coefficients

$\dfrac { 2 }{ 1+\sqrt { 1-4x } } =\displaystyle \sum _{ n=0 }^{ \infty }{ { C }_{ n } } { x }^{ n }$

which can be rewritten as

$\dfrac { 1 }{ 2 } -\dfrac { 1 }{ 2 } \sqrt { 1-\dfrac { 4 }{ a } } =\dfrac { 1 }{ a } \displaystyle \sum _{ n=0 }^{ \infty }{ \left( \dfrac { { C }_{ n } }{ { a }^{ n } } \right) }$

The left side is one of the roots of the equation

${ ax }^{ 2 }-ax+1=0$

and here, in this problem, $a=1000000$

So, the distinct appearances of Catalan numbers ends when

${ C }_{ 14 }=2674440>1000000$

runs into ${ C }_{ 13 }=742900<1000000$

so that the answer is $12$

It's a little surprising to see Catalan numbers pop out of such a simple equation.

Exactly what I had in mind, no need for me to write another solution.

Haroun Meghaichi - 5 years, 11 months ago

If distinct means no zero between, l agree.

Martin Bittcher - 3 years, 7 months ago

To prove the digits of $C_1, \:\ldots,\:C_{12}$ are unaffected by the rest of the sum. we must show $\sum_{k=13}^\infty C_k10^{-6(k+1)}\in \left[0;\: 10^{-78}\right)\quad (*)$

It is not enough to verify $C_{14}$ only overlaps with $C_{13}$ . Even if that were the case, the combined rest in $(*)$ could still grow big enough to influence any digit before - including those of $C_1,\:\ldots,\:C_{12}$ .

Rem.: Let's prove a sufficient upper estimate of the combined rest with $a_k := C_k10^{-6(k+1)}$ and $k\geq 13$ : $\begin{aligned} \left|\frac{a_{k+1}}{a_k}\right| &= \frac{(2k+2)(2k+1)}{(k+1)^210^6}=\frac{4}{10^6}\cdot\frac{2k+1}{2k+2}<\frac{4}{10^6}<\frac{1}{9}=:q,&&& |a_k|&\leq|a_{13}|q^{k-13},\\\\ \sum_{k=13}^\infty a_k &<|a_{13}|\sum_{k=13}^\infty q^{k-13}=\frac{|a_{13}|}{1-q}=C_{13}\cdot 10^{-84}\cdot\frac{9}{8}<10^{-78}\quad_\blacksquare \end{aligned}$

Carsten Meyer - 2 months, 2 weeks ago

K T
Aug 17, 2019

The Catalan numbers are given by $C(n)=\frac{(2n)!}{(n+1!)n!}$ for $n>=0$ and are $1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ...$

The numberst start to overlap as soon as they get more than 6 digits, so that the leading $2$ of $2674440$ merges with the last digit of the 14th Catalan number $C(13)=742900$ into $742902$ (which then of course is not a Catalan number anymore).

Before that were 13 undistorted Catalan numbers, of which $\boxed{12}$ are distinct.

It can undoubtedly be shown that in a Taylor expansion of $\sqrt{x}$ in 1 the Catalan numbers show up, but I considered it a given in this context.

Is this a coincidence too?

Image Credit: Wikimedia Dmharvey .

The answer is 12.

2 solutions

0 pending reports