19
$\begingroup$

It is well known that $$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}... =\log(2).$$
If we consider the array: $T(n,k) = -(n-1)\; \text{ if }\; n|k, \;\text{ else } \;1,$

Starting:

$$\displaystyle T = \left( \begin{array}{ccccccc} +0&+0&+0&+0&+0&+0&+0&\cdots \\ +1&-1&+1&-1&+1&-1&+1 \\ +1&+1&-2&+1&+1&-2&+1 \\ +1&+1&+1&-3&+1&+1&+1 \\ +1&+1&+1&+1&-4&+1&+1 \\ +1&+1&+1&+1&+1&-5&+1 \\ +1&+1&+1&+1&+1&+1&-6 \\ \vdots&&&&&&&\ddots \end{array} \right)$$


Is it true that $\displaystyle \log(n)=\sum\limits_{k=1}^{\infty}\frac{T(n,k)}{k}$$\;$?

|cite|improve this question
$\endgroup$
  • $\begingroup$ And why do you expect this to hold (e.g. you computed the partial sums up to a big number and they are close to the $\log$s...)? $\endgroup$ – Marek Jun 19 '11 at 23:36
  • 1
    $\begingroup$ Why's this tagged as number-theory? $\endgroup$ – George Lowther Jun 20 '11 at 1:46
  • $\begingroup$ @Marek & @George Lowther: Perhaps not an answer to your questions, but this recurrence here: list.seqfan.eu/pipermail/seqfan/2011-June/014999.html , led me to the values of the Mangoldt function here: list.seqfan.eu/pipermail/seqfan/2011-June/015006.html , which in turn led me to the series above. $\endgroup$ – Mats Granvik Jun 20 '11 at 8:07
  • $\begingroup$ right, thanks. I'm glad it wasn't just a guess because to me the limit was quite unapparent (although I admit I am ignorant and series like these might be well-known). $\endgroup$ – Marek Jun 20 '11 at 8:59
  • 1
    $\begingroup$ We can see the formula for log(k) in page 136 by Lehmer (1975) matwbn.icm.edu.pl/ksiazki/aa/aa27/aa27121.pdf $\endgroup$ – Jaume Oliver Lafont Feb 4 '16 at 11:34
22
$\begingroup$

You can write $T(n,k)=1-n1_{\{n\mid k\}}$. Then, for $\vert x\vert < 1$ look at the power series $$ \begin{align} \sum_{k=1}^\infty\frac{T(n,k)}{k}x^k&=\sum_{k=1}^\infty\frac{x^k}{k}-\sum_{k=1}^\infty1_{\{n\mid k\}}\frac{nx^k}{k}\\ &=\sum_{k=1}^\infty\frac{x^k}{k}-\sum_{k=1}^\infty\frac{x^{nk}}{k}\\ &=-\log(1-x)+\log(1-x^n)\\ &=\log\left(\frac{1-x^n}{1-x}\right)\\ &=\log(1+x+\cdots+x^{n-1}). \end{align}. $$ So, letting $x$ increase to 1, $$ \lim_{x\uparrow1}\sum_{k=1}^\infty\frac{T(n,k)}{k}x^k=\log n. $$ The fact that you can commute this limit with the summation to get $\sum_{k=1}^\infty T(n,k)/k$ follows from the fact the series converges uniformly (over $0 < x < 1$). You can show this by grouping together the consecutive positive terms where $n\nmid k$ to get a sequence with alternating signs and decreasing in magnitude. Then, truncating the series gives an error which is bounded by the following term. That is, $$ \left\vert\sum_{k=1}^{jn-1}\frac{T(n,k)}{k}x^k-\log(1+x+\cdots+x^{n-1})\right\vert \le \frac{-T(n,jn)}{jn}x^{jn}\le \frac1j. $$ Commuting the limit with a finite sum is no problem, so you get $$ \left\vert\sum_{k=1}^{jn-1}\frac{T(n,k)}{k}-\log n\right\vert\le\frac1j. $$

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ Very nice derivation from basic principles. $\endgroup$ – André Nicolas Jun 20 '11 at 1:43
6
$\begingroup$

Yes. You can get the sums by differentiating the digamma function repeatedly. There is a good deal of information about the resulting polygamma functions, including series expressions, here. Your matrix version is a lot more visually arresting than the usual Dirac delta function formulation!

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I'd still like to know how one comes up with such series and a conjecture of what they should converge to. Any clues? $\endgroup$ – Marek Jun 20 '11 at 1:07
  • $\begingroup$ @Marek: (This is only speculation.) There is a long history of evaluation of $\Gamma$, $\Gamma'/\Gamma$, and their derivatives at special points. So the answers ($\log n$) may have come before the questions (series). $\endgroup$ – André Nicolas Jun 20 '11 at 1:51
  • $\begingroup$ @AndréNicolas When you say resulting polygamma functions, what do you mean? I am trying to find a relationship between n/LambertW(n)-1 and Stirling numbers of the second kind. In the derivative of the explicit formula for Stirling numbers of the second kind I get the polygamma function, according to Mathematica. How do you find the polygamma function in relation to this question about logarithms? $\endgroup$ – Mats Granvik Oct 18 '13 at 12:09
  • $\begingroup$ After some experimenting, I find that $$\sum _{n=0}^{\infty } \left(\frac{x^{2 n+1}}{(2 n+1)^s}-\frac{x^{2 n+2}}{(2 n+2)^s}\right) = 2^{-s} \left(x \Phi \left(x^2,s,\frac{1}{2}\right)-\text{Li}_s\left(x^2\right)\right)$$ where $\text{Li}_s\left(x^2\right)$ is the PolyLog function and $\Phi \left(x^2,s,\frac{1}{2}\right)$ is the LerchPhi function. Is this what you meant in your answer above? $\endgroup$ – Mats Granvik Oct 18 '13 at 12:16
1
$\begingroup$

@Marek,

For me the hint was in http://oeis.org/A097321, from which the numerators for log(3) are 1,1,-2.

Now log(2) having 1, -1

and log(3) having 1, 1, -2

suggests the pattern.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

The formula seem to be extendable to fractional arguments of the log. The key is to rewrite the formula for $\log(x)$ as difference of two sums but to a common limit. So we can write $$ \begin{eqnarray} \log(x) &=& \lim_{n\to \infty} \sum_{k=1}^n {1 \over k} - x\sum_{k=1}^{\lfloor n/x \rfloor} {1 \over x k} \\ &=& \lim_{n\to \infty} \sum_{k=1}^n {1 \over k} - \sum_{k=1}^{\lfloor n/x \rfloor} {1 \over k}\\ &=& \lim_{n\to \infty} \sum_{k=\lfloor n/x \rfloor+1}^n {1 \over k} \end{eqnarray} $$ It seems to be a possible improvement to take the mean of the two sums when the initial index is either $ \lfloor n/x \rfloor $ or $ \lfloor n/x \rfloor +1 $ . So the final best (but not too complicated) approximation might be $$ \begin{eqnarray} w_n &=& \lfloor n/x \rfloor\\ \log(x) &=& \lim_{n\to \infty} {1\over2w_n} + \sum_{k=w_n+1}^n {1 \over k} \end{eqnarray} $$ However, for reasonable digits of precision one needs many many terms, so this might be only of formal interest.
Moreover, maybe the formula in this notation is also known; I vaguely think I've seen series-formulae involving the floor-function in this or related ways...

[update] There is one more...
To think of fractional summation-bounds suggests to consider integration instead of sums. So I tried $$ \log(x) = \lim_{n \to \infty} \int_{n/x} ^n \frac 1t dt $$ and then even $$ \log(x) = \lim_{n \to \infty} \int_n^{nx} \frac 1t dt $$ and after that even could let n finite...
and the perfect result (even for small n) $$ \log(x) \underset{n \gt 0}{=} \int_n^{nx} \frac 1t dt $$ suggests to look into wikipedia to see, who had noticed that first... ;-) and it's nice to see the identity of the integral-definition and the simple reformulation and generalization of your surprising patterns.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

For computing $log(\frac{p}{q})$ we can take $p$ positive terms from the harmonic series and $n$ negative ones at each step.

$$ \log\left(\frac{p}{q}\right)=\sum_{i=0}^\infty \left(\sum_{j=pi+1}^{p(i+1)}\frac{1}{j}-\sum_{k=qi+1}^{q(i+1)}\frac{1}{k}\right) $$

Sequence https://oeis.org/A166871 in the OEIS illustrates case $\frac{p}{q}=\frac{3}{2}$

This generalizes by using sequences as summation limits: https://math.stackexchange.com/a/1609512/134791

|cite|improve this answer
$\endgroup$

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.