I've been reading through Wilf's Generatingfunctionology a bit, and have come back to the binomial relation he works out early on (p.14). Basically, he takes the recurrence relation of coefficients: $$ b_{n,k}=b_{n-1,k}+b_{n-1,k-1} $$ an does the generating function magic of summing both sides by $k$-indexed powers of $x$, and using the definition of $B_n(x)=\sum_{k \geq 0} b_{n,k} \ x^k$ gets the following (with $B_0=1$): $$ B_{n}(x)=B_{n-1}(x)+xB_{n-1}(x) \\ B_{n}(x)=(1+x)B_{n-1}(x) \\ B_{n}(x)=(1+x)^n $$ This is all well and good, and modifying a few small things I worked backward to find out that $$ C_{n}(x)=(1-x)^n \quad \longleftrightarrow \quad c_{n,k}=c_{n-1,k}-c_{n-1,k-1} $$ which is great. Everything is making perfect sense still. However, when I'm looking at another similar generating function I'm having trouble working backward to an original coefficient recurrence relation. $$ F_{n}(x)=(\sqrt{1+x})^n \quad \longleftrightarrow \quad f_{n,k} \ = \ ??? $$ When I try to simplify by removing the radical when dropping two levels of $n$, I'm left with: $$ F_{n}(x)=(1+x)F_{n-2} \quad \longleftrightarrow \quad f_{n,k}= f_{n-2,k}+f_{n-2,k-1} $$ The steps all make sense, but I'm thrown off by the fact that if I follow those same steps, then: $$ G_{n}(x)=(-\sqrt{1+x})^n \quad \longleftrightarrow \quad g_{n,k}= g_{n-2,k}+g_{n-2,k-1} $$ which is the exact same recurrence!

Shouldn't I be getting different recurrences for these two different generating functions? My results seem to just ignore the odd-$n$ contributions for either generating function.


$F$ and $G$ have the same recurrence? Of course they do. $F_n(x)=G_n(x)$ if $n$ is even, and $F_n(x)=-G_n(x)$ if $n$ is odd. On the other hand, the even-$n$ case simplifies to $F_{2k}(x)=(1+x)^k$, which we know already; it's the odd $n$ that we care about.

The difference between the two systems is not in the recurrences, but in the initial conditions. The even $n$ case has initial condition $F_0(x)=G_0(x)=1$, while the odd $n$ case has initial condition $F_1(x)=\sqrt{1+x}$ and $G_1(x)=-\sqrt{1+x}$. We need two initial conditions because of the way we step $n$ by two at a time.

  • $\begingroup$ Thank you for the reply. The fact that the even cases are matching is comfortable, but I still do not like the fact that I have to just 'know' the form of $F_1(x)$. For example, going back to the binomial example, one could write $B_n(x)=(1+x)^2 B_{n-2}(x)$ and put themselves in a similar predicament. $\endgroup$ – AmateurDotCounter Mar 9 at 23:07
  • $\begingroup$ Isn't there some way to translate $F_n(x)$ into a coefficient recurrence relation $f_{n,k}=???$ that explicitly mentions the $f_{n-1,k}$ terms? $\endgroup$ – AmateurDotCounter Mar 9 at 23:10
  • $\begingroup$ Yes, but. The catch is that if we're multiplying by $\sqrt{1+x}$, that recurrence will have infinite depth, and we still need to know the series of $\sqrt{1+x}$ to get it. Remember, we alternate between a series for which all but finitely many coefficients are zero and one with all coefficients nonzero. $\endgroup$ – jmerry Mar 9 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.