# How to prove this equality $t(1-t)^{-1}=\sum_{k\geq0} 2^k t^{2^k}(1+t^{2^k})^{-1}$?

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

-

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.

-
Everything dies and kills sound so dramatic. –  Pedro Tamaroff Apr 24 '12 at 18:03
It's tradition - compare the title of ams.org/mathscinet/search/… –  Neal Apr 24 '12 at 20:32
-1 The formal proof is incorrect since you make no mention of convergence, a common error. –  Gone 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. –  Gone 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$.

-

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

-
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). –  Gone 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. –  Gone Apr 24 '12 at 21:30
show 1 more comment

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

-
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