3
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
3
  • $\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$
    – DotCounter
    Commented Mar 9, 2019 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$
    – DotCounter
    Commented Mar 9, 2019 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
    Commented Mar 9, 2019 at 23:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .