Number of digits in row of Pascal's triangle is $O\left(n^2\right)$

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

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

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

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