5
$\begingroup$

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.

4 Answers 4

8

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.

  • 1
    It's tradition - compare the title of http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Milnor&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=137&mx-pid=1306962012-04-24
2

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

2

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

  • 0
    OH! My bad! I didn't read the problem stemed from a book on ADVANCED COMBINATORICS. BTW; Are you interested in reading/revising a proof I wrote about the power series of $\sin x$ and $\cos x$? (The proof is novel, as far as I know)2012-04-24
0

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
    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?2012-04-24