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.

  • 2
    `Everything dies` and `kills` sound so dramatic.2012-04-24
  • 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
    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)2012-04-24
  • 0
    Why is it necessary to make a distinction between formal series and functional series here?2012-04-24
  • 0
    @Peter I said nothing about functional series, only formal power series (being from a combinatorics textbook, this is probably the intended denotation).2012-04-24
  • 0
    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.`?2012-04-24
  • 0
    @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.2012-04-24
  • 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