Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
Everything dies and kills sound so dramatic. – Pedro Tamaroff Apr 24 '12 at 18:03
It's tradition - compare the title of… – Neal Apr 24 '12 at 20:32
-1 The formal proof is incorrect since you make no mention of convergence, a common error. – Bill Dubuque Apr 24 '12 at 20:40
I made explicit mention of convergence. But feel free to downvote, at least this time you did not do it anonymously. – André Nicolas Apr 24 '12 at 20:44
There is no mention of convergence as a formal power series, see my answer. Please do not make false accusations. – Bill Dubuque Apr 24 '12 at 20:47

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$.

share|cite|improve this answer

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}$$

share|cite|improve this answer
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) – Pedro Tamaroff Apr 24 '12 at 21:04
Why is it necessary to make a distinction between formal series and functional series here? – Pedro Tamaroff Apr 24 '12 at 21:08
@Peter I said nothing about functional series, only formal power series (being from a combinatorics textbook, this is probably the intended denotation). – Bill Dubuque Apr 24 '12 at 21:23
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.? – Pedro Tamaroff Apr 24 '12 at 21:25
@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. – 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}$$

share|cite|improve this answer
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? – Robert Israel Apr 24 '12 at 18:13

Your Answer


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.