1
$\begingroup$

Let $a_n$ be the number of decimal digits in the $n$-th row of Pascal's Triangle (so $a_0=1, a_1=2, a_2=3, a_3=4, a_4=5, a_5=8,\dots$).

Prove that $\frac{a_n}{n^2}$ converges and find the limit.

It's very easy to see that it converges. Indeed, it's well known that $\binom{2n}{n}\sim\frac{4^n}{\sqrt{\pi n}}$ as $n\to\infty$. Letting $b_n=\log_{10}\binom{2n}{n}$, clearly $a_n\leq(n-2)b_n+2$. Then \begin{align*}\lim_{n\to\infty}\frac{a_n}{n^2}&\leq\lim_{n\to\infty}\frac{\log_{10}\frac{4^n}{\sqrt{\pi n}}}{2n}\\&=\lim_{n\to\infty}\frac{4n\ln(2)-1}{4n\ln(10)}\\&=\frac{\ln(2)}{\ln(10)}\approx0.301\dots\end{align*} However, empirical testing up to $2000$ suggests that this is a bad bound, and indeed, I'm sure that we can do a lot better, especially as I don't think $a_n\to(n-2)b_n+2$ as $n\to\infty$.

$\endgroup$
  • $\begingroup$ you might try to approximate $\sum_k (\log_{10} (2n ; k) +1)$ by a gaussian integral $\endgroup$ – H. H. Rugh Aug 27 '16 at 20:15
  • $\begingroup$ Technically, your argument doesn't show that it converges—just that its lim sup is finite. (Maybe it oscillates around as $n$ grows....) $\endgroup$ – Greg Martin Aug 27 '16 at 22:01
2
$\begingroup$

The quantity you're investigating is $\displaystyle \sum_{k=0}^n \left( \lfloor \frac{\ln \binom{n}{k} }{\ln 10}\rfloor +1\right) = n + O(n) + \frac{1}{\ln 10}\sum_{k=0}^n \ln \binom{n}{k} $

A simple computation yields $\displaystyle \frac{1}{n^2}\sum_{k=0}^n \ln \binom{n}{k} = \frac 2n \sum_{k=1}^n \frac kn \ln\left( \frac kn\right) + \frac{n+1}{n^2}\ln\left(\frac{n^n}{n!}\right)$

First term is a Riemann sum that goes to $-\frac 12$, and the second term goes to $1$ (with Stirling).

Hence $$\begin{align}\displaystyle \sum_{k=0}^n \left( \lfloor \frac{\ln \binom{n}{k} }{\ln 10}\rfloor +1\right) &= n + O(n) + \frac 1{2\ln 10} n^2 + o(n^2)\\ &= \frac 1{2\ln 10} n^2 + o(n^2)\end{align}$$


Telescopic estimates for $\sum_{k=1}^n k\ln k$ yield $\displaystyle \sum_{k=1}^n k\ln k=\frac{n^2\ln n}2 - \frac{n^2}4 +\frac{n\ln n}{2} + o(n\ln n)$

Since $\displaystyle\sum_{k=0}^n \ln \binom{n}{k} = -(n+1)\ln(n!)+2\sum_{k=1}^n k\ln k$, we get the sharper estimate $$\displaystyle \sum_{k=0}^n \left( \lfloor \frac{\ln \binom{n}{k} }{\ln 10}\rfloor +1\right) = \frac 1{2\ln 10} n^2 - \frac{1}{2\ln(10)}\frac{\ln n}{n} + o\left(\frac{\ln n}{n} \right)$$

$\endgroup$
  • $\begingroup$ Can we adapt your argument to find a numerical value for the limit? $\endgroup$ – jlammy Aug 27 '16 at 21:21
  • 1
    $\begingroup$ @jlammy I've computed the limit, it's $\frac 12$ ... $\endgroup$ – Gabriel Romon Aug 27 '16 at 21:22
  • $\begingroup$ wait but I've just realised I can lower my estimate by a factor of $2$ down to $0.301\dots$? $\endgroup$ – jlammy Aug 27 '16 at 21:47
  • 2
    $\begingroup$ For the first equality, shouldn't there be a factor $\frac{1}{\ln 10}$ before the last term? $\endgroup$ – Clement C. Aug 28 '16 at 1:26
  • $\begingroup$ @ClementC. yes, my bad $\endgroup$ – Gabriel Romon Aug 28 '16 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.