# Summing up the series $a_{3k}$ where $\log(1-x+x^2) = \sum a_k x^k$

If $\ln(1-x+x^2) = a_1x+a_2x^2 + \cdots \text{ then } a_3+a_6+a_9+a_{12} + \cdots =$ ?

My approach is to write $1-x+x^2 = \frac{1+x^3}{1+x}$ then expanding the respective logarithms,I got a series (of coefficient) which is nothing but $\frac{2}{3}\ln 2$.But this approach took some time for me (I can't solved it during the test but after the test I solved it)... Any other quick method?

-

Lemma: Let $f(x) = \sum a_n x^n$ be a power series. Then

$$\sum a_{3n} x^{3n} = \frac{f(x) + f(\omega x) + f(\omega^2 x)}{3}$$

where $\omega = e^{ \frac{2\pi i}{3} }$.

Proof. Ignoring convergence it suffices to prove this for a single term, and then it boils down to the identity

$$\frac{1 + \omega^n + \omega^{2n}}{3} = \begin{cases} 1 \text{ if } 3 | n \\\ 0 \text{ otherwise} \end{cases}.$$

This is a special case of the discrete Fourier transform. Applying the lemma, we readily obtain that the desired sum is

$$\frac{\ln 1 + \ln (1 - \omega + \omega^2) + \ln (1 - \omega^2 + \omega)}{3} = \frac{1}{3} \ln (2 \omega^2 \cdot 2 \omega) = \frac{2}{3} \ln 2$$

where we use the fact that $1 + \omega + \omega^2 = 0$.

-
@Debanjan: how are you doing anything with power series without learning about convergence and divergence? Anyway, try doing it with polynomials first. – Qiaochu Yuan Nov 24 '10 at 20:21
@Qiaochu: Nice general method! Thanks! – user1119 Nov 24 '10 at 21:18
A small remark (also related to DFT of course): Just like an analytic function can be split into an even and on odd part, $f(z) = \frac12 (f(z)+f(-z)) + \frac12 (f(z)-f(-z))$, whose power series contain only even and odd powers of $z$, respectively, one can also split it into three parts containing powers $z^{3k}$, $z^{3k+1}$ and $z^{3k+2}$, respectively, by a similar trick where the square roots of one ($\pm 1$) are replaced by the cube roots of one ($1$, $\omega$, $\omega^2$): (cont.) – Hans Lundmark Nov 24 '10 at 21:47
(cont.) $f(z) = \frac13 (f(z) + f(\omega z) + f(\omega^2 z)) + \frac13 (f(z) + \omega^2 f(\omega z) + \omega f(\omega^2 z)) + \frac13 (f(z) + \omega f(\omega z) + \omega^2 f(\omega^2 z))$. If a function lacks terms of the form $z^{3k+2}$, then it will have the symmetry property $f(z) + \omega f(\omega z) + \omega^2 f(\omega^2 z) = 0$; an example of such a function is the Airy function $\mathrm{Ai}(z)$. – Hans Lundmark Nov 24 '10 at 21:47
(cont.) The Airy function is a solution to $f''(z)=z f(z)$. Substituting a power series ansatz into the ODE shows that each coefficient determines the coefficients three steps further down the series, and since $f''(0)=0$, the coefficient $a_2$ is zero, and this forces all coefficients $a_{3k+2}$ to be zero. – Hans Lundmark Nov 24 '10 at 21:51

Qiaochu Yuan gives an excellent exposition of the general method. Sometimes in specific cases you can get the answer via some hands-on calculations as well, and expanding the logs as you mentioned can actually be done pretty quickly: using that $1 - x + x^2 = {1 + x^3 \over 1 + x}$ one gets that $\ln(1 - x + x^2) = \ln(1 + x^3) - \ln(1 + x)$. You now can use the fact that the sum of $a_3 + a_6 + ...$ is obtained by subtracting the corresponding sums for $\ln(1 + x^3)$ and $\ln(1 + x)$. Since the power series for $\ln(1 + x^3)$ only contains powers of $x^3$, the contribution to $a_3 + a_6 + ...$ coming from that term is what you get from plugging in $x = 1$, namely $\ln(2)$.

The power series of $\ln(1 + x)$ may be written as $-\sum_{n > 0} {(-x)^n \over n}$. Taking every third term gives $-\sum_{n > 0} {(-x)^{3n} \over 3n} = -{1 \over 3}\sum_{n > 0} {(-x^3)^n \over n}$. Note this series is again the series of $\ln(1 + x)$, but applied to $x^3$ in place of $x$. Plugging in $x = 1$ gives ${1 \over 3}\ln(2)$.

So the answer you want is $\ln(2) - {1 \over 3}\ln(2) = {2 \over 3}\ln(2)$.

-

Generally one can employ evaluations at roots of unity to take arbitrary such multisections of power series. See my post here and the links there for discussion and examples. Generally, if we let $\rm\:w\:$ denote a primitive $\rm n$'th root of unity, then the $\rm m$'th $\rm n$-section of a power series selects the linear progression of $\rm\: m + k\:n\:$ indexed terms, viz. if $\rm\ f\:(X)\ =\ a_0 + a_1 X + a_2 X^2 +\: \cdots\$ then

$\rm\quad\quad\quad\quad\quad a_{m}\ X^m + a_{m+n}\ X^{m+n} + a_{m+2n}\ X^{m+2n}\ +\: \cdots$

$\rm\quad\quad\displaystyle\ =\ \frac{1}n\: (\:f\:(X) + f\:(Xw)\ w^{-m} + f\:(X\:w^2)\ w^{-2m} +\:\cdots\: \:+\ f\:(X\:w^{n-1})\ w^{(1-n)\:m}\:)$

See Riordan's classic textbook "Combinatorial Identities" for many applications of multisections.

-