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

Question

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.

Answer 1

$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.