# Recurrence Relation from Generating Function: $F_{n}(x)=(\sqrt{1+x})^n$

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.
• 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. – AmateurDotCounter Mar 9 at 23:07
• 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? – AmateurDotCounter Mar 9 at 23:10
• 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. – jmerry Mar 9 at 23:12