1
$\begingroup$

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

Out of curiosity, continuing off of the linked question, I present the following question:

What is the asymptotic growth of the sum of all the digits in the $n^{\text{th}}$ row of Pascal's Triangle, when all the binomial coefficients are written in base $b$?

It can be assumed that $b$ is a positive integer.

$\endgroup$
1
$\begingroup$

You can assume that most of the digits are random, so if there are $m$ digits in the sum, the sum of digits is about $\frac {b-1}2m$. The leading digits may be biased low, but there are only $n$ leading digits in row $n$, so the non-leading digits will dominate. The sum of digits is then $\frac {b-1}2 n^2 \in O( n^2)$

$\endgroup$
  • $\begingroup$ If we assumed each digit was random, then wouldn't the sum be the average digit multiplied by the number of digits? $\endgroup$ – Jack Lam Aug 29 '16 at 4:51
  • $\begingroup$ In that case, why isn't the sum of digits asymptotic to $n^2$, just like the number of digits? $\endgroup$ – Jack Lam Aug 29 '16 at 10:01
  • $\begingroup$ I had confused myself into taking the number of digits in $n^2$. Fixed $\endgroup$ – Ross Millikan Aug 29 '16 at 14:52

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.