Concatenating Pascal's Triangle

Calculus Level 5

Consider

the following sequence ( A003590 ): $1, 11, 121, 1331, 14641, 15101051, 1615201561, \ldots$

where the $n^\text{th}$ term is the concatenation of all integers in the $n^\text{th}$ row of the Pascal's Triangle in that order, beginning with $n=0$ .

Let $L_n$ be the number of digits in the $n^\text{th}$ term of this sequence.

Compute $\displaystyle \lim_{n\to\infty}\exp\left(\frac{n^2}{L_n}\right)$ .

Notation : $\exp(x)$ denotes the exponential function, $\exp(x) = e^x$ .

Image Credit: N. J. A. Sloane

The answer is 100.

1 solution

Michael Mendrin
Feb 9, 2016

If the apex of Pascal’s Triangle is the $0$ th row, then the $k$ th element of the $nth$ row of same can be expressed as

$\left( \begin{matrix} n \\ k \end{matrix} \right) =\dfrac { n! }{ k!(n-k)! }$

where $k$ ranges from $0$ to $n$

The number of digits of any large integer $p$ is approximately

$\dfrac { Log\left( p \right) }{ Log\left( 10 \right) }$

The sum of the digits of all the elements of the $n$ th row then is approximately

$\displaystyle \sum _{ k=0 }^{ n }{ \frac { Log\left( \left( \begin{matrix} n \\ k \end{matrix} \right) \right) }{ Log\left( 10 \right) } }$

$\dfrac { 1 }{ Log\left( 10 \right) }\displaystyle \sum _{ k=0 }^{ n }{ Log\left( \left( \begin{matrix} n \\ k \end{matrix} \right) \right) }$

${ L }_{ n }=\dfrac { 1 }{ Log\left( 10 \right) } Log\left(\displaystyle \prod _{ k=0 }^{ n }{ \left( \begin{matrix} n \\ k \end{matrix} \right) } \right)$

Thus we have

$\large { e }^{ \frac { { n }^{ 2 } }{ { L }_{ n } } }=\large { 10 }^{ \frac { { n }^{ 2 } }{ Log\left( P \right) } }$

where $P$ is the product of all the elements of the $n$ th row. If

$Q=\large { P }^{ \frac { 1 }{ { n }^{ 2 } } }$

this becomes

$\large { 10 }^{ \frac { 1 }{ Log\left( Q \right) } }$

To find the limiting value as $n\rightarrow \infty$ , we start with $P$ , which is equal to all of the following expressions

$\displaystyle \prod _{ k=0 }^{ n }{ \dfrac { n! }{ k!\left( n-k \right) ! } }$

${ \left( n! \right) }^{ n+1 }\displaystyle \prod _{ k=0 }^{ n }{ \dfrac { 1 }{ k!\left( n-k \right) ! } }$

${ \left( n! \right) }^{ n+1 }{ \left(\displaystyle \prod _{ k=1 }^{ n }{ k! } \right) }^{ -2 }$

$\left(\displaystyle \prod _{ k=1 }^{ n }{ \dfrac { { k }^{ n+1 } }{ k! } } \right) { \left(\displaystyle \prod _{ k=1 }^{ n }{ k! } \right) }^{ -1 }$

$\left(\displaystyle \prod _{ k=1 }^{ n }{ { k }^{ k } } \right) { \left(\displaystyle \prod _{ k=1 }^{ n }{ k! } \right) }^{ -1 }$

Because they all equal the same value $P$ , from the $3$ rd and $5$ th expressions we have the following

$P={ \left( n! \right) }^{ -\left( n+1 \right) }{ \left( \displaystyle \prod _{ k=1 }^{ n }{ { k }^{ k } } \right) }^{ 2 }$

The product in this expression is the HyperFactorial, which has the asymptotic value for large $n$

$\displaystyle \prod _{ k=1 }^{ n }{ { k }^{ k } } \sim A\cdot { n }^{ \frac { 1 }{ 2 } n\left( n+1 \right) +\frac { 1 }{ 12 } }\cdot { e }^{ -\frac { { n }^{ 2 } }{ 4 } }$

where $A=1.28242712…$ is the Glaisher-Kinkelin Constant

Along with this, we use Stirling’s Approximation to write out $Q={ P }^{ \frac { 1 }{ { n }^{ 2 } } }$ in full

${ \left( { \left( \sqrt { 2\pi n } { \left( \frac { n }{ e } \right) }^{ n } \right) }^{ -\left( n+1 \right) }{ \left( A\cdot { n }^{ \frac { 1 }{ 2 } n\left( n+1 \right) +\frac { 1 }{ 12 } }\cdot { e }^{ -\frac { { n }^{ 2 } }{ 4 } } \right) }^{ 2 } \right) }^{ \frac { 1 }{ { n }^{ 2 } } }$

The limiting value of this expression as $n\rightarrow \infty$ is $Q=\sqrt{e}$ . $\;$ We then compute the final answer

$\large { 10 }^{ \frac { 1 }{ Log\left( Q \right) } }=100$

Moderator note:

Playing devils advocate, we have to be careful with the calculation for the number of digits, as we only have an under-estimate.

Furthermore, even if $f_n \sim g_n$ , it does not imply that $e ^ { f_n} \sim e ^ { g_n}$ .

awesome solution!

Hamza A - 5 years, 4 months ago

Playing devils advocate, we have to be careful with the calculation for the number of digits, as we only have an under-estimate.

Furthermore, even if $f_n \sim g_n$ , it does not imply that $e ^ { f_n} \sim e ^ { g_n}$ .

Calvin Lin Staff - 5 years, 3 months ago

I'll get back to you about the matter of the need for a very good approximation of number of digits of a number a bit later, as that is really the crux of the problem. However, I'm not sure what you refer to in your 2nd comment. The problem asks for the limiting value of ${e}^{{f}_{n}}$ , and if that ${f}_{n}$ has a definite finite limit as $n\rightarrow \infty$ , then shouldn't ${e}^{{f}_{n}}$ be the correct result? For example, suppose ${f}_{n}=0$ as a limiting value, then shouldn't this be true, ${e}^{{f}_{n}}=1$ ?

Let's say we have the plot of the exponential function ${e}^{x}$ , and let $f$ and $g$ initially not necessarily have the exact same numerical value. Positive reals, to keep this simpler. We plot the points $\left(f, {e}^{f}\right)$ and $\left(g, {e}^{g}\right)$ . So, let $g$ approach $f$ in some kind of a limiting matter. When $f,g$ finally agree exactly, then ${e}^{f}, {e}^{g}$ agree exactly also. This works because the exponential function is a continuous, differentiable function.

Indeed, the core of the problem is the asymptotic behavior the number of digits in a row of Pascal's Triangle. The use of the exponential is a way of expressing that asymptotic behavior, which is related to the fact it's expressed in decimal format. Had it been binary, then the answer would have been $4$ --which corresponds with a considerable increase in digits.

Edit: Okay, for any positive integer $p$ , the number of digits $n$ it has is always

$\dfrac { Log\left( p \right) }{ Log\left( 10 \right) } \le n\le \dfrac { Log\left( p \right) }{ Log\left( 10 \right) } +1$

so that the maximum error is $n+1$ in the digit count of the $n$ th row of Pascal's Triangle. This $n+1$ should then be added or subtracted from $P$ in the solution give above, which will turn out to have no affect on the result either way.

Michael Mendrin - 5 years, 3 months ago

Hm, not sure what I meant by my second comment. The implication is true.

Right, to be pedantic, we have to chase down the effect of the $+ 1$ . However, we only have $n+1$ terms of these $+ 1$ , but there is a $n^2$ term in the numerator, so the effect is negligible.