Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

if $n$ is very big how to prove that number of 0 digits in rightward of $n!$ exactly equal is $[\frac n4]$ it's mean : $ \lim_{n\to \infty} \frac{E_5(n!)}{[\frac n4]} =1$

that $E_5(n!)= \sum_{k=1}^\infty [\frac{n}{5^k}]$

it's proved that that number of 0-digits in rightward of $n!$ is $E_5(n!)$

I tried to prove it by sandwich theorem.

$E_5(n!) \le \frac n5+\frac {n}{5^2}+...=n\frac{\frac 15}{1-\frac 15}= \frac n4$ rightward of sandwich theorem is provided. leftward? how?

$$(??\le \frac{E_5(n!)}{[\frac n4]} \le 1 )$$

share|improve this question
    
What does "in rightward of $n!$" mean? (haven't seen that term.) –  coffeemath Mar 16 '13 at 20:51
    
it means the largest power of 10 that divides n!. The number of trailing zeroes. –  Bananarama Mar 16 '13 at 21:21

4 Answers 4

up vote 0 down vote accepted

I think you might want to show that: $\frac{[n/4]-C(n)}{[n/4]}\le \frac{E_5(n!)}{[n/4]} \le 1$, where lim $\frac{C(n)}{[n/4]} =0$ and by taking the limit, you can use the Sandwich method.

In order to prove the above, you need to show $E_5(n!) + C(n) \ge [\frac{n}{4}]$

It is equivalent to saying that $C(n) + [n/5]+[n/5^2]+....\ge [n/5+n/5^2+...]$ (*) So you need to find C(n) so when you add it to $E_5(n!)$, you have the above.

There is a fact, which is not hard to prove: $1+[x_1]+[x_2]\ge[x_1+x_2]$. From this, you can generalize it to more variables: $k-1+[x_1]+[x_2]+...+[x_k]\ge [x_1+x_2+...+x_k]$

In the (*) above, look at the left side, there are only a finite number K of terms of the forms $[n/5^k]$ which are different from 0. This K is ~ $log_5$ n. Using the inequality, you have:

K-1 + $[n/5]+[n/5^2]+...+[n/5^K]\ge[n/5+n/5^2+..+n/5^K]$

The tail: $n/5^{K+1}+n/5^{K+2}+...= n/5^{K+1} * (\frac{1}{1-1/5}) < 1 * 5/4 = 5/4 $

From here, you have: 3+ (K-1) + $[n/5]+[n/5^2]+...+[n/5^K]\ge[n/5+n/5^2+..+n/5^K+....]$ So take C(n) = K+2, and you are done.

share|improve this answer

As discussed here, the number of factors of $5$ in $n!$ is $$ \frac{n-\sigma_5(n)}{4}\tag{1} $$ where $\sigma_5(n)$ is the sum of the base $5$ digits of $n$. Since the number of factors of $2$ that divide $n!$ is about 4 times the number of factors of $5$, there will be an ample number to match the $5$s. For example, in $3124!$ there are $776$ zeros to the right, whereas $\frac{3124}{4}=781$.

Now $\sigma_5(n)\le4(\lfloor\log_5(n)\rfloor+1)$ (the maximum digit times the number of digits); therefore, $$ \frac n4-\lfloor\log_5(n)\rfloor-1\le\frac{n-\sigma_5(n)}{4}\le\frac n4\tag{2} $$ Since $$ \lim_{n\to\infty}\frac{\log_5(n)}{n}=0\tag{3} $$ the Squeeze Theorem and $(2)$ and $(3)$ give your result.

share|improve this answer

You guys are doing too much work...

In order for $n!$ to have a zero at the end, it must include a number of 2's and 5's. There are more 2's than there are 5's for any factorial, so counting the number of 5's in $n!$ will tell you the number of 0's at the end of $n!$.

So the numbers of 5's will be represented by $⌊\frac{n}{5}⌋$. However, this doesn't include the extra 5's from other powers of 5. like 25. The number of extra 5's would be $⌊\frac{n}{25}⌋$.

Continuing this pattern infinitely is simply a geometric series $$\frac{\frac{1}{5}n}{1-\frac{1}{5}} = \frac{1}{4}n$$

share|improve this answer
    
This is not exact; as I computed above, $3124!$ has $776$ zeros on the right, $5$ fewer than $\frac{3124}{4}=781$. This error needs to be controlled to get the limit. –  robjohn Mar 17 '13 at 1:47

Suppose that the base five representation of $n$ is $$ n = \sum_{k=0}^{\lfloor \log_5 n\rfloor} d_k 5^k.$$ Then it is not difficult to see that $$E_5(n!) = -n + \sum_{k\ge 0} \Big\lfloor \frac{n}{5^k} \Big\rfloor = -n + \sum_{j=0}^{\lfloor \log_5 n\rfloor} \sum_{k=j}^{\lfloor \log_5 n\rfloor} d_k 5^{k-j}.$$ Let $$T(n) = \sum_{j=0}^{\lfloor \log_5 n\rfloor} \sum_{k=j}^{\lfloor \log_5 n\rfloor} d_k 5^{k-j}.$$ Now clearly the minimum for $T(n)$ is attained when $n$ consists of a single one digit followed by zeros, giving $$ T(n) \ge \sum_{j=0}^{\lfloor \log_5 n\rfloor} 5^{\lfloor \log_5 n\rfloor-j} = 5^{\lfloor \log_5 n\rfloor} \sum_{j=0}^{\lfloor \log_5 n\rfloor} 5^{-j} = \frac{1}{4} 5^{\lfloor \log_5 n\rfloor+1} - \frac{1}{4} = \frac{5}{4} n \left(5^{\lfloor \log_5 n\rfloor-\log_5 n} - \frac{1}{5n}\right) = \frac{5}{4} n \left(1 - \frac{1}{5n}\right). $$ The last equality occurs because for $n$ as described, the floor of the logarithm stays exact.

The maximum is attained when all digits are equal to four, giving $$ T(n) \le \sum_{j=0}^{\lfloor \log_5 n\rfloor} 4 \sum_{k=j}^{\lfloor \log_5 n\rfloor} 5^{k-j} = \frac{1}{4} 5^{\lfloor \log_5 n\rfloor+2} -\lfloor \log_5 n\rfloor - \frac{9}{4} = \frac{5}{4} n \left(5^{\lfloor \log_5 n\rfloor+1-\log_5 n} -\frac{4}{5}\frac{\lfloor \log_5 n\rfloor}{n} - \frac{9}{5n}\right). $$

Now the asymptotics require some work here. With all digits equal to four, we have $$ n= 5^{\lfloor \log_5 n\rfloor+1} -1.$$ It follows that $$ 5^{\lfloor \log_5 n\rfloor+1-\log_5 n} = 5^{\lfloor \log_5 n\rfloor+1-\log_5 \left(5^{\lfloor \log_5 n\rfloor+1} -1\right) } = \frac{5^{\lfloor \log_5 n\rfloor+1}}{5^{\lfloor \log_5 n\rfloor+1}-1} \\ = \frac{1}{1-1/5^{\lfloor \log_5 n\rfloor+1}} = 1 + \left(\frac{1}{5^{\lfloor \log_5 n\rfloor+1}}\right) + \left(\frac{1}{5^{\lfloor \log_5 n\rfloor+1}}\right)^2 + \left(\frac{1}{5^{\lfloor \log_5 n\rfloor+1}}\right)^3 + \cdots.$$ This yields the following asymptotic expansion for the upper bound: $$ T(n) \le \frac{5}{4} n \left(1 + \left(\frac{1}{5^{\lfloor \log_5 n\rfloor+1}}\right) + \left(\frac{1}{5^{\lfloor \log_5 n\rfloor+1}}\right)^2+\cdots -\frac{4}{5}\frac{\lfloor \log_5 n\rfloor}{n} - \frac{9}{5n}\right).$$ Finally, taking the upper bound and the lower bound together we have shown that $$ T(n) \sim \frac{5}{4} n $$ and hence $$ E_5(n!) \sim \frac{1}{4} n.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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