Geometric Combinatorics

Proposition 4.1.2: The sets \((M)\), \((\gamma)\), \((\Delta)\), and \((h^*)\) are bases for the vector space \(\mathbb{C}[x]_{\le d} := \{f \in \mathbb{C}[x] : \deg(f)\le d\}.\)
Proposition 4.1.3: A sequence \(f(n)\) is given by a polynomial of degree \(\le d\) if and only if \((\Delta^m f)(0)=0 \) for all \(m>d\).
If \(f(n) = \binom{n}{m}\), then \( F(z) = \sum_{n \geq 0} \binom{n}{m} z^n = \frac{z^m}{(1-z)^{m+1}} \)
Proposition 4.1.4: A sequence \(f(n)\) is given by a polynomial of degree \(\le d\) if and only if \[ \sum_{n\ge 0} f(n)z^n = \frac{h(z)}{(1-z)^{d+1}} \] for some polynomial \(h(z)\) of degree \(\le d\). Furthermore, \(f(n)\) has degree \(d\) if and only if \(h(1)\neq 0\).
Proposition 4.1.5: Let \((f(n))_{n\ge0}\) be a sequence of numbers. Then \((f(n))_{n\ge0}\) satisfies a linear recurrence of the form (4.1.10) (with \(c_0,c_d\neq0\)) if and only if \[ F(z)=\sum_{n\ge0} f(n)z^n =\frac{p(z)}{c_d z^d+c_{d-1}z^{d-1}+\cdots+c_0} \] for some polynomial \(p(z)\) of degree \(< d\).