What happens with indexes in this proof? 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?
 A: 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.
A: 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.
