jmc

The first few terms are $$\begin{array}{rl}{x}_2& =\frac{(n-1)\cdot 1-(n-k)\cdot 0}{1}=n-1,\\ x_3& =\frac{(n-1)(n-1)-(n-1)\cdot 1}{2}=\frac{(n-1)(n-2)}{2},\\ x_4& =\frac{(n-1)\cdot \frac{(n-1)(n-2)}{2}-(n-2)(n-1)}{3}=\frac{(n-1)(n-2)(n-3)}{6}.\end{array}$$It looks like $$x_k=\frac{(n-1)(n-2)\cdots (n-k+1)}{(k-1)!}$$for $k\ge 2.$ We prove this by induction.

We see that the result holds for $k=2$ and $k=3,$ so assume that the result holds for $k=i$ and $k=i+1$ for some $i\ge 2,$ so $$\begin{array}{rl}{x}_i& =\frac{(n-1)(n-2)\cdots (n-i+1)}{(i-1)!},\\ x_{i+1}& =\frac{(n-1)(n-2)\cdots (n-i+1)(n-i)}{i!}.\end{array}$$Then $$\begin{array}{rl}{x}_{i+2}& =\frac{(n-1)x_{i+1}-(n-i)x_i}{i+1}\\ & =\frac{(n-1)\cdot \frac{(n-1)(n-2)\cdots (n-i+1)(n-i)}{i!}-(n-i)\cdot \frac{(n-1)(n-2)\cdots (n-i+1)}{(i-1)!}}{i+1}\\ & =\frac{(n-1)(n-2)\cdots (n-i+1)(n-i)}{(i-1)!}\cdot \frac{(n-1)/i-1}{i+1}\\ & =\frac{(n-1)(n-2)\cdots (n-i+1)(n-i)}{(i-1)!}\cdot \frac{n-1-i}{i(i+1)}\\ & =\frac{(n-1)(n-2)\cdots (n-i+1)(n-i)(n-i-1)}{(i+1)!}.\end{array}$$This completes the induction step.

It follows that $$x_k=\frac{(n-1)(n-2)\cdots (n-k+1)}{(k-1)!}=\frac{(n-1)!}{(k-1)!(n-k)!}=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$$for $k\le n,$ and $x_k=0$ for $k\ge n+1.$ Therefore, $$x_0+x_1+x_2+\cdots =\left(\genfrac{}{}{0ex}{}{n-1}{0}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{1}\right)+\left(\genfrac{}{}{0ex}{}{n-2}{2}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n-1}{n-1}\right)=\boxed{2^{n-1}}.$$