Prove the equality $\quad t(1-t)^{-1}=\sum_{k\geq0} 2^k t^{2^k}(1+t^{2^k})^{-1}$.

I have just tried to use the Taylor's expansion of the left to prove it.But I failed.

I don't know how the $k$ and $2^k$ in the right occur. And this homework appears after some place with the $Jacobi$ $Identity$ in the book $Advanced$ $Combinatorics$(Page 118,EX10 (2)).

Any hints about the proof ?Thank you in advance.


It is clearer without the summation symbol. We want to find $$\frac{t}{1+t}+\frac{2t^2}{1+t^2}+\frac{4t^4}{1+t^4}+\frac{8t^8}{1+t^8}+\frac{16t^{16}}{1+t^{16}}+\cdots.\tag{$\ast$}$$ Add $\dfrac{-t}{1-t}$ on the left. Note that $$\frac{-t}{1-t}+\frac{t}{1+t}=\frac{-2t^2}{1-t^2}.$$ But $$\frac{-2t^2}{1-t^2}+\frac{2t^2}{1+t^2}=\frac{-4t^4}{1+t^4}\quad\text{and}\quad \frac{-4t^4}{1-t^4}+\frac{4t^4}{1+t^4}=\frac{-8t^8}{1+t^8}.$$ Continue. So adding $\dfrac{-t}{1-t}$ kills the sum $(\ast)$, and therefore our sum must be $\dfrac{t}{1-t}$.

To put it another way, the sum $(\ast)$ is almost a telescoping series. All it needed was a little nudge.

The calculation above is a formal manipulation. However, the series $(\ast)$ converges whenever $|t|<1$, so the formal manipulation gives the correct answer.


This is all for $|t|<1$. Start with the geometric series $$\frac{t}{1-t} = \sum_{n=1}^\infty t^n$$ On the right side, each term expands as a geometric series $$\frac{2^k t^{2^k}}{1+t^{2^k}} = \sum_{j=1}^\infty 2^k (-1)^{j-1} t^{j 2^k}$$ If we add this up over all nonnegative integers $k$, for each integer $n$ you get a term in $t^n$ whenever $n$ is divisible by $2^k$, with coefficient $+2^k$ when $n/2^k$ is odd and $-2^k$ when $n/2^k$ is even. So if $2^p$ is the largest power of $2$ that divides $n$, the coefficient of $t^n$ will be $2^p -\sum_{k=0}^{p-1} 2^k = 1$.


Hint $\ $ Let $\rm\:N\to\infty\ $ in $\rm\displaystyle\ \sum_{K\!\:=\!\:0}^{N-1}\!\ \frac{2^{\:\!K}\:\! t^{2^{\:\!K}}}{t^{2^K}\!+1} + \frac{t}{t-1}\: =\ \frac{2^{\:\!N}\:\! t^{2^{\:\!N}}}{t^{2^{\:\!N}}\!-1}\ =\: c\ t^{2^{\:\!N}} + \:\cdots\ $ by telescopy.

Since $\rm\: t^{2^{\:\!N}} \to 0\:$ as $\rm\:N\to \infty,\:$ the desired formal power series equality follows.

See here for more on convergence of formal power series (beware many make errors here).

Remark $\ $ The telescopic proof is simply $\rm 2^{\:\!N}$ times below, for $\rm\:x = t^{2^N}$

$$\rm \frac{2\:x^2}{x^2-1} - \frac{x}{x-1}\: =\: \frac{x}{x+1}$$

  • $\begingroup$ It is funny many people usually make problems regarding series more difficult by letting partial sums aside. They really come in handy in most cases I have seen so far. (+1) $\endgroup$ – Pedro Tamaroff Apr 24 '12 at 21:04
  • $\begingroup$ Why is it necessary to make a distinction between formal series and functional series here? $\endgroup$ – Pedro Tamaroff Apr 24 '12 at 21:08
  • $\begingroup$ @Peter I said nothing about functional series, only formal power series (being from a combinatorics textbook, this is probably the intended denotation). $\endgroup$ – Bill Dubuque Apr 24 '12 at 21:23
  • $\begingroup$ I meant, usual series versus formal series. I was reading about them and the word slipped. I'm talking about when you say the desired formal power series equality follows. Why is it not the desired power series equality follows.? $\endgroup$ – Pedro Tamaroff Apr 24 '12 at 21:25
  • $\begingroup$ @Peter Yes, I know. I chose to work with formal power series, not functional power series, because that is usually what is desired in combinatorics. $\endgroup$ – Bill Dubuque Apr 24 '12 at 21:30

You can use:

$$\frac{t}{t-1} = \sum_{n=1}^\infty{t^n}=t+t^2+(t^3+t^4)+(t^5 + ... + t^8)$$ And then use: $$\sum_{n=2^k}^{n=2^{k+1}}{t^{n}} = \frac{t^{2^k}(t^{2^{k+1}}-1)}{t-1}$$

  • 1
    $\begingroup$ That's not quite right. For one thing $$ \sum_{n=2^k}^{2^{k+1}} t^n = {\frac {{t}^{{2}^{k+1}+1}-{t}^{{2}^{k}}}{t-1}}$$ And how would that relate to the desired form? $\endgroup$ – Robert Israel Apr 24 '12 at 18:13

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.