# Infinite sum of $n^kx^n$

To "solve" this problem, I will consider the following geometric series, of course, |x|<1:

$S=1+x+x^2+x^3+\cdots=\sum\limits^{\infty}_{n=0}x^n$

$xS=x+x^2+x^3+\cdots=\sum\limits^{\infty}_{n=1}x^n=\left(\sum^{\infty}_{n=1}x^n\right)+x^0-x^0=\left(\sum\limits^{\infty}_{n=0}x^n\right)-1=S-1$

$xS=S-1$

$1=S-Sx$

$1=(1-x)S$

$S=\frac{1}{1-x}=\sum\limits^{\infty}_{n=0}x^n$

This answers the question for $k=0$, to solve this for other $k$, I will do the derivative of both sides, before that, I will use the following "formula", to help get things done faster(I used the Power Rule and the Chain Rule to reach this result without too much work):

$\frac{\mathrm{d}}{\mathrm{d}x}\left[\frac{1}{(1-x)^n}\right]=\frac{n}{(1-x)^{n+1}}$

$\frac{\mathrm{d}}{\mathrm{d}x}\left[\frac{1}{1-x}\right]=\frac{\mathrm{d}}{\mathrm{d}x}\left[\sum\limits^{\infty}_{n=0}x^n\right]$

$\frac{1}{(1-x)^2}=\sum\limits^{\infty}_{n=0}nx^{n-1}$

Now I will multiply everything by $x$, to adjust the right side of the equality:

$\frac{x}{(1-x)^2}=\sum\limits^{\infty}_{n=0}nx^{n}$

I will apply partial fractions on the left side of the equality, using the following formula(you can prove it by simply doing the operations):

$\frac{x}{(1-x)^n}=\frac{1}{(1-x)^n}-\frac{1}{(1-x)^{n-1}}$

Then I get:

$\frac{1}{(1-x)^2}-\frac{1}{1-x}=\sum\limits^{\infty}_{n=0}nx^{n}$

Note to get the answer for $k=2$, I can do the derivative of both sides, then multiply by $x$, and then apply partial fractions, but then I can do for $k=3$ and so on;

Does anyone know how to solve the recurrence relation I get?

Let's suppose that I know the answer for $k=p$, there is a sequence of $A_{p,n}$ as the coefficients of $\frac{1}{(1-x)^n}$ such that:

$\sum\limits^{p+1}_{k=1}\frac{A_{p,k}}{(1-x)^{k}}=\sum\limits^{\infty}_{k=0}k^px^k$

I will do the derivative of both sides:

$\sum\limits^{p+1}_{k=1}\frac{kA_{p,k}}{(1-x)^{k+1}}=\sum\limits^{\infty}_{k=0}k^{p+1}x^{k-1}$

Then I will multiply both sides by $x$:

$\sum\limits^{p+1}_{k=1}\frac{kA_{p,k}x}{(1-x)^{k+1}}=\sum\limits^{\infty}_{k=0}k^{p+1}x^{k}$

Applying partial fractions:

$\sum\limits^{p+1}_{k=1}\frac{kA_{p,k}}{(1-x)^{k+1}}-\sum\limits^{p+1}_{k=1}\frac{kA_{p,k}}{(1-x)^{k}}=\sum\limits^{\infty}_{k=0}k^{p+1}x^{k}$

This is the solution for $k=p+1$, therefore I can say that this is equal to the sum of $\frac{1}{(1-x)^k}$, with the appropriate coefficients $A_{p+1,k}$, also, I will take out the last and first coefficients because they don't have pairs, with that I can say:

$\frac{kA_{p,p+1}}{(1-x)^{p+2}}+\sum\limits^{p+1}_{k=2}\left(\frac{(k-1)A_{p,k-1}}{(1-x)^{k}}-\frac{kA_{p,k}}{(1-x)^{k}}\right )-\frac{A_{p,1}}{1-x}=\sum\limits^{\infty}_{k=0}k^{p+1}x^{k}=\sum\limits^{p+2}_{k=1}\frac{A_{p+1,k}}{(1-x)^{k}}$

With this, I can say some things:

$A_{p+1,p+2}=(p+1)A_{p,p+1}$

$A_{p+1,1}=-A_{p,1}$

$A_{p+1,k}=(k-1)A_{p,k-1}-kA_{p,k}$

There are some patterns I can see(they can be proved by induction):

$A_{p,p+1}=p!$

$A_{p,1}=(-1)^n$

$A_{p,p}=-\frac{(p+1)!}{2}$

But I can't give a complete closed "simple" formula, like Faulhaber's Formula, does anyone know or has a suggestion to tackle this problem?

Note by Matheus Jahnke
3 years, 6 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

The recurrence sequence can be expressed in terms of Stirling Numbers of the Second Kind.

$\sum _{k=0}^{\infty} k^n x^k = \sum_{k=0}^n k! \; S(n+1,k+1) \left( \dfrac x{1-x} \right)^{k+1}$

- 3 years, 6 months ago

Absolutely, but I have not been able (yet) to obtain a closed expression the coefficients of $\tfrac{1}{(1-x)^k}$. There is an obvious formula in terms of Stirling numbers and Binomial coefficients...

- 3 years, 6 months ago

Apparently $\sum_{k = 1}^\infty k^n x^k = \sum_{k = 1}^{n + 1} \frac{(-1)^{n + k + 1} S(n + 1,k) (k - 1)!}{(1 - x)^k}.$

- 3 years, 6 months ago

And here is a proof by induction: It is easy to verify that the formula holds for $n = 1$, so assume that it holds for some positive integer $n$, i.e. $\sum_{k = 1}^\infty k^n x^k = \sum_{k = 1}^{n + 1} \frac{(-1)^{n + k + 1} S(n + 1,k) (k - 1)!}{(1 - x)^k}.$

Differentiating both sides, we get $\sum_{k = 1}^\infty k^{n + 1} x^{k - 1} = \sum_{k = 1}^{n + 1} \frac{(-1)^{n + k + 1} S(n + 1,k) k!}{(1 - x)^{k + 1}},$ so $\sum_{k = 1}^\infty k^{n + 1} x^k = \sum_{k = 1}^{n + 1} \frac{(-1)^{n + k + 1} S(n + 1,k) k! x}{(1 - x)^{k + 1}}.$

We can write $\frac{x}{(1 - x)^{k + 1}} = \frac{(x - 1) + 1}{(1 - x)^{k + 1}} = \frac{1}{(1 - x)^{k + 1}} - \frac{1}{(1 - x)^k},$ so \begin{aligned} &\sum_{k = 1}^{n + 1} \frac{(-1)^{n + k + 1} S(n + 1,k) k! x}{(1 - x)^{k + 1}} \\ &= \sum_{k = 1}^{n + 1} \left( \frac{(-1)^{n + k + 1} S(n + 1,k) k!}{(1 - x)^{k + 1}} - \frac{(-1)^{n + k + 1} S(n + 1,k) k!}{(1 - x)^k} \right) \\ &= \frac{(-1)^{n + 1}}{1 - x} + \sum_{k = 2}^{n + 1} \left( \frac{(-1)^{n + k} S(n + 1,k - 1) (k - 1)!}{(1 - x)^k} - \frac{(-1)^{n + k + 1} S(n + 1,k) k!}{(1 - x)^k} \right) + \frac{(n + 1)!}{(1 - x)^{n + 2}} \\ &= \frac{(-1)^{n + 1}}{1 - x} + \sum_{k = 2}^{n + 1} \frac{(-1)^{n + k} (k - 1)!}{(1 - x)^k} [S(n + 1,k - 1) + kS(n + 1,k)] + \frac{(n + 1)!}{(1 - x)^{n + 2}} \\ &= \frac{(-1)^{n + 1}}{1 - x} + \sum_{k = 2}^{n + 1} \frac{(-1)^{n + k} S(n + 2,k) (k - 1)!}{(1 - x)^k} + \frac{(n + 1)!}{(1 - x)^{n + 2}} \\ &= \sum_{k = 1}^{n + 2} \frac{(-1)^{n + k} S(n + 2,k) (k - 1)!}{(1 - x)^k}. \end{aligned} This completes the induction step.

- 3 years, 6 months ago

This is an interesting question. My first thought is Falling factorials, but I don't think that's helpful.

Summoning @Mark Hennings + @Ishan Singh

- 3 years, 6 months ago

There is a chance of this(or the Rising Factorial) being helpful:

$\frac{1}{1-x}=\sum\limits^{\infty}_{n=0}x^n$

$\frac{\mathrm{d}^{p-1}}{\mathrm{d}^{p-1}x}\left[\frac{1}{1-x}\right ]=\frac{\mathrm{d}^{p-1}}{\mathrm{d}^{p-1}x}\left[\sum\limits^{\infty}_{n=0}x^n \right ]$

$\frac{(p-1)!}{(1-x)^p}=\sum\limits^{\infty}_{n=0}(n)_px^{n-p+1}$

$\frac{(p-1)!}{(1-x)^p}=\sum\limits^{\infty}_{n=0}n^{(p)}x^{n}$

Well, consider the following question: how we can determine the coefficients $C_{p,n}$ such that:

$\sum\limits^{p}_{k=1}C_{p,k}x^{(k)}=x^p$

This question is closely related to the problem I discussed earlier, because then $A_{p,n}=(n-1)!C_{p,n}$

- 3 years, 6 months ago

This problem may be easier to tackle because it has an easier recurrence relation:

$x^{(n)}=x(x+1)(x+2)\cdots x(x+n-1)$

$(x+n)x^{(n)}=x^{(n+1)}$

$x^{(n)}x+nx^{(n)}=x^{(n+1)}$

$x^{(n)}x=x^{(n+1)}-nx^{(n)}$

Now, trying to find the recurrence around $C_{p,n}$:

$\sum\limits^{p}_{k=1}C_{p,k}x^{(k)}=x^p$

Multiplying everything by $x$:

$\sum\limits^{p}_{k=1}C_{p,k}x^{(k)}x=x^{p+1}$

Using the recurrence of the Rising Factorial:

$\sum\limits^{p}_{k=1}C_{p,k}(x^{(k+1)}-kx^{(k)})=x^{p+1}$

$\sum\limits^{p}_{k=1}C_{p,k}x^{(k+1)}-\sum\limits^{p}_{k=1}C_{p,k}kx^{(k)}=x^{p+1}$

I will take the first and last terms because they don't have pairs:

$x^{(p+1)}C_{p,p}+\sum\limits^{p}_{k=2}x^{(k)}(C_{p,k-1}-kC_{p,k})x^{(k)}-C_{p,1}=x^{p+1}$

With that I can say:

$C_{p+1,p+1}=C_{p,p}$

$C_{p+1, k}=C_{p,k-1}-kC_{p,k}$

$C_{p+1,1}=-C_{p,1}$

Again, I can find some patterns that can be proved by induction:

$C_{n,n}=1$

$C_{n,n-1}=-\frac{n(n-1)}{2}$

$C_{n,1}=(-1)^{n+1}$

- 3 years, 6 months ago