Generatingfunctionology Chapter 1 Exercise 9

Question

Regarding the exercises of the Generatingfunctionology book available at (https://www2.math.upenn.edu/~wilf/DownldGF.html).

In particular Chapter 1, Exercise 9 (page 25).

First part: Here a function $f$ is defined for $n\geq 1$ as (a) $f(1)=1$, (b) $f(2n) = f(n)$, (c) $f(2n+1) = f(n) + f(n+1)$. And the generating function of the sequence is defined as $$F(x) = \sum_{n\geq 1} f(n) x^{n-1}.$$ I must show that $$F(x) = (1+x+x^2)F(x^2).$$

1. First $F(x^2) = \sum_{n\geq 1} f(n) x^{2n-2}$. Then, I started by applying the techniques of "The Method" (page 8) to (c) and got: $$f(2n+1) = f(n) + f(n+1) \Rightarrow \sum_{n\geq 1} f(2n+1) x^{2n+1} = \sum_{n\geq 1} f(n) x^{2n+1} + \sum_{n\geq 1} f(n+1) x^{2n+1} $$ From here, by changing variables $m=2n+1$ and $l = n+1$, I got: $$\sum_{m\geq 3} f(m) x^m = \sum_{n\geq 1} f(n) x^{2n+1} + \sum_{l\geq 2} f(l)x^{2l-1}$$ $$x \sum_{m\geq 1} f(m) x^{m-1} - f(1) x - f(2) x^2 = x^3 \sum_{n\geq 1} f(n) x^{2n-2} + x\sum_{l\geq 1} f(l)x^{2l-2} - f(1)x$$ which substituting by $F(x), F(x^2)$ and since $f(1)=1$ and $f(2n)=f(n), f(2)=f(1)$, $$xF(x) - x - x^2 = x^3F(x^2)+xF(x^2) - x $$ $$F(x) = (x^2 + 1) F(x^2) + x. $$
2. Second, applying "The Method" to (b): $$f(n) = f(2n) \Rightarrow \sum_{n\geq 1} f(n) x^{2n} = \sum_{n\geq 1} f(2n) x^{2n}$$ Again, changing variables $m=2n$, $$\sum_{n\geq 1} f(n) x^{2n} = \sum_{m\geq 2} f(m) x^{m}$$ $$x^2\sum_{n\geq 1} f(n) x^{2n-2} = x\sum_{m\geq 1} f(m) x^{m-1} - f(1)x$$ $$ x^2 F(x^2) = xF(x) - x$$ $$ x F(x^2) = F(x) - 1$$
3. Combining both, I got $$ 2F(x) -x -1 = (x^2 + x + 1)F(x^2).$$

Clearly, something I did is incorrect, but I cannot figure out what. I appreciate any help.

Second part: I must show the general formula $F(x) = \prod_{j\geq 0}^\infty \left(1 + x^{2^{j}} + x^{2^{j+1}}\right)$. By substituting, it is clear that the formula is true. However, how would I start to prove this formaly? The solution says to "consider the product as a formal beast which obviously satisfies the functional equation for $F$", but I don't know what this means nor can I found it online. Could you clarify me what does "consider the product as a formal beast" mean?

Again, I appreciate any help.

Answer 1

I believe with the help of the people from the comments to my question (namely @ancientmathematician, @JBL, @Alexander Burstein) I can post an answer for completion and to check it as answered.

First part: As pointed out, it was a simple mistake of changing variables of the summation without taking into account that I was adding some terms by doing this, which account for the wrong factors appearing. Indeed, this exercise is easiest solved by taking $$F(x) = \sum_{n\geq 1} f(n) x^{n-1} = \sum_{n\ even}f(n) x^{n-1} + \sum_{n\ odd} f(n) x^{n-1} = \sum_{n\geq 1}f(2n) x^{2n-1} + \sum_{n\geq 0} f(2n+1) x^{2n}$$ and using the given identities to compute the correct result.

Second part: This part was much harder, as I was not aware of the results the author used in their solution, but I found everything I needed on this wikipedia page. Here, the function $F(x)$ converges to $F(x) = \prod_{j\geq 0}^\infty (1+x^{2^j}+x^{2^{j+1}})$ if this product converges to an analytic function (the function $F(x)$ can be checked by repeatedly replacing $x$ by $x^2$ in the provided identity $F(x) = (1+x+x^2)F(x^2)$). Now, taking the logarithm of the product, the convergence problem is mapped to a sum of logarithms, so one converges iff the other does too: $$\log \prod_{j= 0}^\infty (1+x^{2^j}+x^{2^{j+1}}) = \sum_{j=0}^\infty \log(1+x^{2^j}+x^{2^{j+1}}).$$ And by taking $|x|<1$, the limit converges to $\log(1)=0$ so the sum converges (everything is positive as we are dealing with power of 2 exponents). Nevertheless, one can also use the limit comparison test (again see the same wikipedia page), and consider that $\sum_{j=0}^\infty \log(1+p_j)$ converges iff $\sum_{j=0}^\infty p_j$ converges. And here, $p_j = x^{2^j} + x^{2^{j+1}}$, which converges for $|x| < 1$.

Edit: Argument using formal power series:

With the help of kind people in the comments (and Wikipedia), I now believe I understand the formal power series argument for the convergence of the product: For a "large enough" $n$, when multiplying the current polynomial ($\prod_{j=0}^n (1+x^{2^j}+x^{2^{j+1}})$) with the $n+1$ term, the coefficients of the lower degrees terms are not affected (the degrees of the coefficients that change grow exponentially with $j$). I.e., they stabilize, and therefore the series converges. Thanks so much to the people that helped!