Evaluate the sum
$\displaystyle [log_21]+[log_22]+[log_23]+...+[log_22002]$.
Stirling's approximation says that, for large n:
$\displaystyle n! \approx \sqrt{2 \pi n} \frac{n^n}{e^n}$
So
$\displaystyle ln(n!) \approx \frac{1}{2}ln(n) + n~ln(n) - n$
(ignoring the relatively small constant term.)
So using the change of base formula:
$\displaystyle log_2(2002!) \approx \frac{ \frac{1}{2}ln(2002) + 2002 \cdot ln(2002) - 2002}{ln(2)} \approx 19073.6$
-Dan
thanks.
you know what the sad thing is? i learned Stirling's approximation in class just the other day, i should have thought of that. (it was in a probability class, i hate probability by the way)
that number seems a LOT smaller than i thought it would be. why does my calculator have problems spitting that answer out, or anything close to it
If you ever take a Statistical Mechanics course you will forever think of the Stirling approximation. Trust me!
Recall that you are looking at the logarithm of a number. So if $\displaystyle log_x \approx 20000$ then we are talking of an x around $\displaystyle 2^{20000}$, a not insignificant number. This is why they invented logs in the first place: early Mathematicians had the TI - 1, which vaguely looks like an abacus with a plug. They couldn't handle multiplication of big numbers. Logarithms reduce the size of the number you are working with, so you can tabulate them easier. (Then they had the HP - 1, thus losing the ability to even count, and we entered the Dark Ages.)
-Dan
I was wondering whether $\displaystyle [x]$ denotes floor function or something like that, because it's a bit strange that perash used it for each term.
It is more interesting if it is the floor function
If it really denotes floor function, to calculate the sum, we should consider
$\displaystyle \sum_{k=1}^{n}{k\cdot{2^k}}$
$\displaystyle \sum_{k=1}^{n}{k\cdot{x^k}}=x\cdot{\left(\sum_{k=0 }^{n}{x^k}\right)'}$
$\displaystyle \sum_{k=1}^{n}{k\cdot{x^k}}=x\cdot{\left(\frac{x^{ n+1}-1}{x-1}\right)'}=x\cdot{\left(\frac{(n+1)x^{n}(x-1)-x^{n+1}+1}{(x-1)^2}\right)}$
$\displaystyle \sum_{k=1}^{n}{k\cdot{2^k}}=(n+1)\cdot{2^{n+1}}-2^{n+2}+2$
Because our sum is: $\displaystyle S=\sum_{k=1}^{10}{k\cdot{2^k}}-(2047-2002)\cdot{10}$
In general
$\displaystyle \sum_{k=1}^{n}{[\log_2(k)]}=\sum_{k=1}^{[\log_2(n)]}{k\cdot{2^k}}-(2^{[\log_2(n)]+1}-1-n)\cdot{[\log_2(n)]}$
Then: $\displaystyle \sum_{k=1}^{n}{[\log_2(k)]}=([\log_2(n)]+1)\cdot{2^{[\log_2(n)]+1}}-2^{[\log_2(n)]+2}+2-(2^{[\log_2(n)]+1}-1-n)\cdot{[\log_2(n)]}$
Which is:
$\displaystyle \sum_{k=1}^{n}{[\log_2(k)]}=-2^{[\log_2(n)]+1}+2+(n+1)\cdot{[\log_2(n)]}$