What happens with indexes in this proof?

Question

I am trying to understand a proof we did in our discrete math class.

Theorem: For $n \geq 0,$ $$x^{\overline{n}} = \sum_k s(n,k) x^k,$$ where $x^\overline{n} = x (x+1)\cdots (x+n-1)$ and $s(n,k)$ is the Stirling number of the first kind.

Proof: We prove the theorem by induction. For $n=0$ we get $1$ on both sides of the equation. So it remains to show $n-1 \to n$. $$ \begin{align} x^{\overline{n}} &= x (x+1) \cdots (x+n-1) \\ &= (x+n-1)\cdot x^{\overline{n-1}} \\ &= (x+n-1)\sum_ks(n-1,k)x^k \\ &= x \sum_ks(n-1,k )x^k + (n-1)\sum_ks(n-1,k)x^k \\ &= \sum_k s(n-1,k)x^{k+1} + (n-1) \sum_k s(n-1,k)x^k \\ &\stackrel{?}{=} \sum_k s(n-1,k-1)x^k + \sum_k (n-1) s(n-1,k)x^k \\ &= \sum_k (s(n-1, k-1) + (n-1)s(n-1,k))x^k \\ &= \sum_k s(n,k)x^k \end{align}$$

The part which confuses me is marked with "$?$". It seems like there was some shift in indexes, which is further made unclear because the notation on $\sum$ simply states $k$ instead of where the $k$ is running from/to.

This is how I understand it: $k$ runs from $1$ to $n$ (or simply $0$ for $n=0$). So we have: $$ \begin{align} &\sum_{k=1}^{n} s(n-1,k)x^{k+1} + (n-1) \sum_{k=1}^n s(n-1,k)x^k \\ =& \sum_{k=2}^{n+1} s(n-1,k-1)x^k + \sum_{k=1}^n (n-1) s(n-1,k)x^k \end{align}$$

So how can we add these two sums together? What happens with the indexes and what am I doing wrong?

Answer 1

Your theorem states $x^{\overline{n}} = \sum_k s(n,k) x^k$, but $s(n,k)=0$ if $k\le 0$ or $k>n$, so the theorem should say $x^{\overline{n}} = \sum_{k=1}^n s(n,k) x^k$, as you correctly deduced.

So (the first term in) your question of the summation becomes $$\begin{align} &\sum_{k=1}^{n-1} s(n-1,k)x^{k+1}\\ \stackrel{j=k+1}{=}&\sum_{j=2}^{n} s(n-1,j-1)x^j\\ \stackrel{k=j}{=}& \sum_{k=2}^{n} s(n-1,k-1)x^k \\ =& \sum_{k=1}^{n} s(n-1,k-1)x^k\\ \end{align}$$

Note that the top sum goes to $n-1$ because it comes from $x^{\overline{n-1}}$. The last equality comes from $s(n-1,0)=0$.

In general it's really bad practice to ignore summation boundaries when doing discrete recursions.

Answer 2

We obtain using the recurrence relation \begin{align*} \begin{bmatrix}n\\k\end{bmatrix}&=\begin{bmatrix}n-1\\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}\qquad\qquad n\geq k>0\tag{1}\\ \begin{bmatrix}0\\0\end{bmatrix}&=1\qquad\begin{bmatrix}n\\0\end{bmatrix}=\begin{bmatrix}0\\n\end{bmatrix}=0\qquad\qquad\qquad\ n>0 \end{align*} of the unsigned Stirling numbers of the first kind: \begin{align*} \color{blue}{x^{\overline{n}}}&=x(x+1)\cdots(x+n-1)\\ &=(x+n-1)x^{\overline{n-1}}\\ &=(x+n-1)\sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}x^k\\ &=\sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}x^{k+1} +(n-1)\sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}x^k\\ &=\sum_{k=1}^{n}\begin{bmatrix}n-1\\k-1\end{bmatrix}x^{k} +(n-1)\sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix}x^k\\ &=\begin{bmatrix}n-1\\n-1\end{bmatrix} +\sum_{k=1}^{n-1}\left(\begin{bmatrix}n-1\\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}\right)x^k\\ &\qquad +(n-1)\begin{bmatrix}n-1\\0\end{bmatrix}\\ &=1+\sum_{k=1}^{n-1}\begin{bmatrix}n\\k\end{bmatrix}x^k+0\tag{$\to \mathrm{(1)}$}\\ &\,\,\color{blue}{=\sum_{k=0}^{n}\begin{bmatrix}n\\k\end{bmatrix}x^k} \end{align*} and the induction step follows.