2

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.

Cant
  • 107
  • 2
    When you make the change of variables $m=2n+1$ etc you then write $\sum_{m\ge 3}$ forgetting that you only have the odd indexed terms; similarly in the second part. That's why you are ending up with $2F(x)$ (and I suspect it also gives rise to the extra $x+1$, but i haven't checked that.) To clean this up you should start with $F(x)$,split into the odd and even terms, use the recursions on the odd/even terms and it willdrop out. – ancient mathematician Feb 16 '23 at 16:01
  • 1
    The infinite product $F(x)=\prod_{j=0}^{\infty}\left(1+x^{2^j}+x^{2^{j+1}}\right)$ is a limit, as $n\to\infty$, of finite products $F_n(x)=\prod_{j=0}^{n}\left(1+x^{2^j}+x^{2^{j+1}}\right)$. Since $F_n(x)$ are polynomials, we can prove that they converge as formal power series by showing that their coefficients stabilize, i.e. for any $m\in\mathbb{N}$, there exists $N=N(m)$ such that $[x^m]F_n(x)=[x^m]F_N(x)$ for any $n\ge N$. To show this, note that the degree of the lowest term in each factor $1+x^{2^j}+x^{2^{j+1}}$ is $2^j$, and $2^j\to\infty$ as $j\to\infty$. – Alexander Burstein Feb 17 '23 at 08:14
  • @AlexanderBurstein Just to clarify, I'm assuming that the convergence of the formal power series that you mention is $\sum_{n=1}^\infty F_n(x)$. And, intuitively, you means that from some point on (here $N$), all coefficients of $F_n(x)$ are the same, so the series converges. But is this true if the coefficients "converge" to $\infty$? – Cant Feb 17 '23 at 12:12
  • 2
    Not the convergence of the sum, the convergence of the limit $\lim_{n \to \infty} F_n(x)$. – JBL Feb 17 '23 at 20:42
  • @JBL Right, thanks. But why does it converges if it goes to $\infty$? Does it converge to $\infty$? Also, the degree of the lowest term in each factor shouldn't be zero ($1\cdot1\cdot\dots\cdot 1$)? There should also be a term of degree $1$ ($x\cdot1\cdot\dots\cdot 1$) and so on, or am I mistaken? – Cant Feb 17 '23 at 21:20
  • 2
    @glv Convergence for formal power series means that their coefficient sequences converge, and that means that the coefficient at each power $x^m$ in $F_n(x)$ is eventually constant as $n\to\infty$. And I should have said "lowest degree nonconstant term" earlier, not simply "lowest degree term". – Alexander Burstein Feb 18 '23 at 05:42
  • @AlexanderBurstein Thanks! I believe I was also wrong as $x$ can be taken such that $|x|<1$, so its coefficients shrink exponentially with $n$. But how is the convergence of the formal power series used to show the identity $F(x) = \prod_{j\geq 0}^\infty (1+x^{2^j}+x^{2^{j+1}})$? – Cant Feb 18 '23 at 13:52
  • I added an answer to my own question, thanks everyone for the help! – Cant Feb 19 '23 at 12:02
  • 3
    @glv You can check formally, just by substitution, that $\prod_{j=0}^{\infty}\left(1+x^{2^j}+x^{2^{j+1}}\right)$ satisfies the identity $F(x)=(1+x+x^2)F(x^2)$. Then you need to show that this infinite product "makes sense", i.e. converges as a formal power series. – Alexander Burstein Feb 19 '23 at 20:08
  • 1
    You might like Chapter 3.3 of Sagan's book, available for free here: https://users.math.msu.edu/users/bsagan/Books/Aoc/GSM210.pdf – JBL Feb 24 '23 at 16:47
  • @JBL Thanks! The book looks interesting. Are you familiar with both this book and Generatingfunctionology? How would you say they compare to each other? I believe Generatingfunctionology Chapter 2 also addresses the theory of formal power series, but I haven't got to it yet... – Cant Feb 24 '23 at 20:48
  • 1
    I think that they while they have significant overlap, their philosophies are different. I would describe Sagan as gentler in general. But also I think the relevant section of Sagan addresses specifically the confusion you're having more directly than generatinfunctionology. – JBL Feb 24 '23 at 21:45

1 Answers1

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!

Cant
  • 107
  • 1
    Good. I see that you've chosen to do the last part analytically, and not by a formal power series argument. In your question you seem to ask for an explanation of Wilf's formal power series proof: and @Alexander Burstein cleared that up for you in the comments I hope? – ancient mathematician Feb 19 '23 at 15:31
  • @ancientmathematician Thanks for asking. I'm still somewhat processing the fact that the coefficients stabilize as $2^j \rightarrow \infty$ when $j\rightarrow \infty$, as when talking of formal power series I'm not allowed to consider the convergence of the series. This notion of stabilization is not very intuitive as the exponents do grow exponentially to $\infty$. If you have any input that might help me I would very much appreciate it! (Also, I still don't know what's a "formal beast".) – Cant Feb 19 '23 at 18:19
  • 1
    I think that stabilization is quite intuitive: just think of the distance between two power series as being $\frac{1}{N+1}$ where $N$ is the least natural number $n$ such that $a_n -b_n\ne 0$. In the case to hand the power series [actually polynomial] $P_k(x)=\prod_{j=0}^k \left(1 + x^{2^{j}} + x^{2^{j+1}}\right)$ then differs from $F(x)$ by at most $\frac{1}{k+1}$ so $P_k\to F$ in this topology. – ancient mathematician Feb 20 '23 at 07:43
  • I think my knowledge is somewhat lacking in the formal power series subject. But I don't see how one can argue that $a_N - b_N = 0$ (for a large enough $N$), when both $a_N$ and $b_N$ go to infinity (as $j\rightarrow \infty$), as this subtraction should have no meaning in this setting. Also, why is the distance between two power series $\frac{1}{N+1}$? – Cant Feb 20 '23 at 14:46
  • 1
    That's a definition of distance, and we discuss convergence wrt that definition. As to this, look at https://en.wikipedia.org/wiki/Formal_power_series and especially the bit about topologies, and convergence. [It has a better definition of the metric than I gave]. – ancient mathematician Feb 20 '23 at 15:13
  • Thanks. This is fine regarding distance and I appreciate the reference. But still I keep coming back to the fact that to have $N$ defined it is still needed that at some point $a_N=b_N$, but when $j\rightarrow \infty$, we get "something like" $x^\infty$, which should be the same as $x^{\infty + 1}$. But without setting $|x|<1$ or something outside formal power series theory, this is not so intuitive to me yet (we are comparing $x^\infty$ with $x^{\infty + 1}$ without talking about $x$, and I still find this somewhat odd). – Cant Feb 20 '23 at 16:47
  • 2
    I an sorry, I don't think you are right.. We're talking about $\sum_{0}^{\infty} a_n x^n$, $\sum_{0}^{\infty} b_n x^n$ here. If all $a_n=b_n$ then the distance is $0$, otherwise $N:=\min{ k \mid a_k\ne b_k}$ is well-defined. But the wiki is much clearer than me, so perhaps we should now stop. – ancient mathematician Feb 20 '23 at 17:26