2

in this book (https://www.math.upenn.edu/~wilf/DownldGF.html) I think I get the first example until the point:

$$\frac{G(x)} x = 2G(x) + \frac 1 {1-x}$$

How is this equal to

$$G(x) = \frac x {(1-x)(1-2x)} \text{ ?}$$

$$G(x) = \frac x {(1 - x)^2}$$ right?

Sorry for not posting the whole problem and not formatting the equations properly. I need to get used to write math equations with a keyboard and find a tool to do it easily.

Michael Hardy
  • 1
bencemeszaros
  • 183
  • I can't find any equation like $G(x)/x = 2G(x)$. Do you mean $\frac{A(x)}x=2A(x)+\frac1{1-x}$, on page 4? – Jack M Oct 11 '15 at 10:34
  • Yes, sorry. :) I'm looking at an other source where they use G(x). – bencemeszaros Oct 11 '15 at 10:37
  • The claim would presumably not be that $\displaystyle\frac{G(x)} x = 2G(x) + \frac 1 {1-x}$ is EQUAL to $\displaystyle G(x) = \text{something}$, but rather that $\displaystyle\frac{G(x)} x = 2G(x) + \frac 1 {1-x}\vphantom{\frac\int{\displaystyle\int}}$ is EQUIVALENT to $\displaystyle G(x) = \text{something}$. "Equal" means both expressions represent the same number. "Equivalent" means one statement is true if and only if the other is. ${}\qquad{}$ – Michael Hardy Oct 11 '15 at 13:30
  • Thanks Michael. I'm reading on equal vs equivalent. – bencemeszaros Oct 11 '15 at 13:57

1 Answers1

3

We start with $$\frac{A(x)}{x} = 2A(x) + \frac{1}{1-x}.$$ Subtracting $2A(x)$ from both sides and factoring the LHS gives \begin{equation}A(x)\left(\frac{1}{x}-2\right) = \frac{1}{1-x}.\tag{$\ast$}\end{equation} Noting that $$\frac{1}{x}-2 = \frac{1-2x}{x},$$ dividing both sides of $(\ast)$ by $\frac1{x}-2$ yields $$A(x) = \frac{x}{(1-x)(1-2x)}.$$

  • 1
    I was getting this totally wrong. I did $$G(x)=2xG(x)+\frac{x}{1+x}$$ then I used $G(x)=\frac{x}{(1+x)^{2}}$ in the RHS. Now I'm not exactly sure why I did this. I was reading this post http://math.stackexchange.com/a/735997/279147 and somehow mixed the things togeather. Now I realize $G(x)=\frac{x}{(1+x)^{2}}$ is the generator function for $a_{n}=n$ and $G(x)=\frac{x}{(1-x)(1-2x)}$ is the generator function of $a_{n+1}=2a_{n}+1$. Really big help, thanks! – bencemeszaros Oct 11 '15 at 14:12