Prove by induction a formula for the sum from 1 to ∞ of nkxn

Four of the previous exercise (here, here, here, and here, Section 10.9, Exercises #11 – #14) suggest a formula

$\sum_{n=1}^{\infty} n^k x^n = \frac{P_k (x) }{(1-x)^{k+1}}.$

In the formula $P_k(x)$ indicates a polynomial of degree $k$ , with the term of lowest degree being $x$ and the highest degree term being $x^k$ (we call a polynomial of degree $k$ with highest term $x^k$ a monic polynomial of degree $k$ ). Use mathematical induction to prove this formula, without justifying the manipulations with the series.

Proof. For the case $k = 1$ , we have

$\sum_{n=1}^{\infty} nx^n = \frac{x}{(1-x)^2},$

from the first exercise linked above (Section 10.7, Exercise #11). Letting $P_k (x) = x$ , a degree $k = 1$ polynomial, with term of lowest degree being $x$ and term of highest degree being $x^1 =x$ . Therefore, the statement holds for the case $k = 1$ . Assume then that the statement is true for some $j = k \in \mathbb{Z}_{>0}$ , so

$\sum_{n=1}^{\infty} n^j x^n = \frac{P_j(x)}{(1-x)^{j+1}}.$

Differentiating both sides (assuming without justification that we can do this) we obtain

$\begin{align*} && \sum_{n=1}^{\infty} n^{j+1} x^{n-1} &= \frac{D(P_j(x)) \cdot (1-x)^{j+1} + P_j(x)(j+1)(1-x)^j}{(1-x)^{2j+2}} \\[9pt] \implies && \sum_{n=1}^{\infty} n^{j+1} x^{n-1} &= \frac{D(P_j(x))(1-x) + P_j(x)(j+1)}{(1-x)^{j+2}} \\[9pt] \implies && \sum_{n=1}^{\infty} n^{j+1} x^{n-1} &= \frac{D(x^j + Q_{j-1}(x) + x)(1-x) + (x^j + Q_{j-1}(x) +x)(j+1)}{(1-x)^{j+2}} \intertext{where $Q_{j-1}(x)$ is a polynomial of degree $j-1$} \implies && \sum_{n=1}^{\infty} n^{j+1}x^{n-1} &= \frac{(jx^{j-1} + Q_{j-2}(x) +1) - (jx^j + Q_{j-1}(x) + x) + (j+1)x^j + (j+1)Q_{j-1}(x) + x(j+1)}{(1-x)^{j+2}} \\[9pt] \implies && \sum_{n=1}^{\infty} n^{j+1} x^{n-1} &= \frac{(jx^{j-1} + Q_{j-2}(x) + 1) - (jx^j + Q_{j-1}(x) + x) + (j+1)x^j + (j+1)Q_{j-1}(x) + x(j+1)}{(1-x)^{j+2}} \\[9pt] \implies && \sum_{n=1}^{\infty} n^{j+1} x^{n-1} &= \frac{(jx^{j-1} + Q_{j-2}(x) + 1) - (jx^j + Q_{j-1}(x) + x) + (j+1)x^j + (j+1)Q_{j-1}(x) + x(j+1)}{(1-x)^{j+2}} \\[9pt] \implies && \sum_{n=1}^{\infty} x^{n-1} &= \frac{x^j + Q^*_{j-1} (x) + 1}{(1-x)^{j+1}} \intertext{where $Q^*_{j-1}(x)$ is a polynomial of degree $j-1$} \implies && \sum_{n=1}^{\infty} n^{j+1} x^{n-1} &= \frac{(jx^{j-1} + Q_{j-2}(x) + 1) - (jx^j + Q_{j-1}(x) + x) + (j+1)x^j + (j+1)Q_{j-1}(x) + x(j+1)}{(1-x)^{j+2}} \\[9pt] \implies && \sum_{n=1}^{\infty} n^{j+1}x^{n-1} &= \frac{x^j + Q^*_{j-1} (x) + 1}{(1-x)^{j+1}} \\[9pt] \implies && \sum_{n=1}^{\infty} n^{j+1}x^n &= \frac{P_{j+1}(x)}{(1-x)^{j+2}}. \end{align*}$

where $P_{j+1}(x)$ is a polynomial of degree $j+1$ with the term of lowest degree being $x$ and that of the highest degree being $x^{j+1}$ . Hence, if the statement is true for $j$ then it is true for $j+1$ ; thus, the statement is true for all positive integers $k. \qquad \blacksquare$