I am trying to understand the following passage from my course notes:
Here is Lemma 3.1:
Discussion:
Starting from the beginning, I will try to explain in detail what I think I understand and ask questions where I am confused, and hopefully someone can set me straight.
(One) Where it says "generating funtions... of the form...", what is happening more precisely is that we are operating in some ring $R$, and the generating function $a_0 + a_1x + \dots$ is an element of the formal power series ring $R[[X]]$.
(Two) The "of the form $\frac{1}{(1-x)^n}$" part means that when following the standard multiplication rules for $R[[X]]$, we get that $(a_0 + a_1x + \dots)(1-x)^n = 1$. (I should also say that $(1 - x)^n$ is an element in $R[[X]]$ as well.)
(Three) Lemma 3.1 shows that $a_k = \binom{n - 1 + k}{k}$, so we know the explicit form of $a_0 + a_1x + \dots$. Algebraic manipulation of $\binom{n - 1 + k}{k}$ into $\frac{1}{(n - 1)!}(k + 1)^{(n - 1)}$ is straightforward.
(Four) In the above notes, we are considering $R = \mathbb R$ or $\mathbb C$, so that means $R$ is a field, and we can therefore consider the vector space $R[X]$ over $R$ where we define scalar multiplication in the form $R \times R[X] \to R[X], (\lambda, p) \to \lambda p$, meaning that the formal power series $b_0 + b_1x + \dots \in R[X]$ multiplied by $\lambda \in R$ becomes $\lambda b_0 + \lambda b_1 x + \dots$.
(Five) In our polynomial vector space $V := R[X]$, we are told that $B := \bigl\{ \frac{1}{(n - 1)!}(x + 1)^{(n - 1)}$ for $n = 1, 2, \dots \bigr\}$ are a basis, so we must have $\text{span}(B) = V$. I'm not sure how to show this. I suppose I can show linear independence by taking a finite subset of $B$, call them $v_1, \dots, v_m$, and noting that $\lambda_1 v_1 + \dots + \lambda_m v_m$ is a polynomial of degree equal to the highest degree of the vectors $v_1, \dots, v_m$. If this linear combination equals $0 \in R[X]$, then we must have all $\lambda_1, \dots, \lambda_m = 0 \in R$.
I need to show that $\text{span}(B) = V$ but I am not sure how to do this. I need to show that the intersection of all subspaces $U \subseteq V$ such that $B \subseteq U$ is equal to $V$ itself.
I guess I could suppose that $\text{span}(B) \neq V$, which would mean there were some element $v \in V$ that was not in the intersection of all such $U$. Therefore there is some $U^*$ in the intersection that does not contain $v$.
I want to show that this is a contradiction, meaning that I can create $v$ out of a linear combination of the basis elements in $B$, which will imply that $v \in U^*$, which will prove that $\text{span}(B) = V$.
If $v = c_0 + c_1x + \dots + c_r x^r$, then take the set $b := \bigl\{ \frac{1}{(n - 1)!}(x + 1)^{(n - 1)}$ for $n = 1, 2, \dots r \bigr\}$. This is a finite subset of the basis $B$, so we must have $b \subseteq U^*$.
If $b_i = \frac{1}{(i - 1)!}(x + 1)^{(i - 1)}$ for $i = 1, \dots, r$, then if I pick the right scalars $\lambda_1, \dots, \lambda_r$ I should be able to show that $\lambda_1 b_1 + \dots + \lambda_r b_r = v$. Figuring out the right scalars seems very messy, though. Is there any easy way to find the right scalars?
(Six) Assuming that $B$ is a basis for $V$, I think then notes are trying to explain how we can use this to find the generating function for a sequence defined by $a_n = n^k$ for $n = 0, 1, 2, \dots$ and fixed natural number $k$.
(Note: I think that strictly speaking the generating function for such a sequence will simply be $0^k + 1^k x + 2^k x + \dots$. What the notes really mean is that we can find the compact i.e. finite representation for this generating function, much like how Lemma 3.1 shows that $\binom{0 + n - 1}{0} + \binom{1 + n - 1}{1}x + \dots = \frac{1}{(1 - x)^n}$.)
I don't understand the connection between $a_n = n^k, b_n = \binom{n - 1 + k}{k}$ and $\frac{1}{(1 - x)^k} = b_0 + b_1x + \dots$. Why $n^k$? I guess the idea is that we can write $0^k + 1^k x + 2^k x + \dots$ as a linear combination of terms $\binom{n - 1 + k}{k}$?
(Seven) Regarding the final paragraph concerning complex numbers, first of all I don't understand the substitution $y = cx$ when there no $y$ to be found anywhere. Are we supposed to be looking at $\binom{0 + n - 1}{0} + \binom{1 + n - 1}{1}y + \dots = \frac{1}{(1 - y)^n}$ and simply replace $y$ with $cx$ for $c \in \mathbb C$? Then we are supposed to be able to write $0^k + 1^k cx + 2^k c^2 x + \dots$ as a linear combination of terms $\binom{n - 1 + k}{k}c^n$? Since I can't understand the simpler instance in (Six) I don't think I can understand this part either.
Sorry about the length of this post. I appreciate any feedback.
Edit:
I think where I wrote $\binom{0 + n - 1}{0} + \binom{1 + n - 1}{1}y + \dots = \frac{1}{(1 - y)^n}$ in (Seven), I should have written instead $\binom{k + 0 - 1}{k} + \binom{k + 1 - 1}{k}y + \dots = \frac{1}{(1 - y)^n}$. In other words it is $k$ that is fixed here and $n$ changes for every term in the generating function.
Your first four points are fine; I’ll take your last three points in reverse order.
The last paragraph could have been written more clearly. Yes, the idea is to start with
$$\frac1{(1-y)^k}=\sum_{n\ge 0}\binom{n-1+k}ky^n$$
and substitute $y=cx$, but one really might just as well work directly with $cx$:
$$\begin{align*} \frac1{(1-cx)^k}&=\sum_{n\ge 0}\binom{n-1+k}k(cx)^n\\ &=\sum_{n\ge 0}\binom{n-1+k}kc^nx^n\,, \end{align*}$$
so $\frac1{(1-cx)^k}$ is the generating function for the sequence $\left\langle\binom{n-1+k}kc^n:n\in\Bbb N\right\rangle$.
For $n\in\Bbb N$ let $p_n(x)=\frac1{n!}(x+1)^{\overline{n}}$, and assume that $\{p_n(x):n\in\Bbb N\}$ is a basis for $R[x]$. For each $k\in\Bbb N$ let $q_k(x)=x^k$. Since $\deg p_n(x)=n$, there are constants $c_{k,i}$ for $i=0,\ldots,k$ such that $q_k(x)=\sum_{i=0}^kc_{k,i}p_i(x)$.
$$\begin{align*} \sum_{n\ge 0}n^kx^n&=\sum_{n\ge 0}\sum_{i=0}^kc_{k,i}p_i(n)x^n\\ &=\sum_{i=0}^kc_{k,i}\sum_{n\ge 0}p_i(n)x^n\\ &=\sum_{i=0}^kc_{k,i}\sum_{n\ge 0}\frac1{i!}(n+1)^{\overline{i}}x^n\\ &=\sum_{i=0}^kc_{k,i}\sum_{n\ge 0}\binom{n+i}nx^n\\ &=\sum_{i=0}^k\frac{c_{k,i}}{(1-x)^{i+1}}\,, \end{align*}$$
so that $\sum_{i=0}^k\frac{c_{k,i}}{(1-x)^{i+1}}$ is the generating function for the sequence $\langle n^k:n\in\Bbb N\rangle$.
Probably the easiest way to see that $\{p_n(x):n\in\Bbb N\}$ is a basis for $R[x]$ is to observe that $\deg p_n(x)=n$ for each $n\in\Bbb N$; an easy induction on $k$ then shows that $q_k(x)=x^k\in\operatorname{span}\{p_n(x):n\in\Bbb N\}$ for each $k\in\Bbb N$. The actual coefficients in the linear combinations are a bit messy and involve Stirling numbers of the first kind.