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?

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 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"

Math

Appears 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}

Easy Math Editor

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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}$

Ishan Singh - 3 years, 9 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...

Mark Hennings - 3 years, 9 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}.$

Jon Haussmann - 3 years, 9 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.

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

Summoning @Mark Hennings + @Ishan Singh

Pi Han Goh - 3 years, 9 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}$

Matheus Jahnke - 3 years, 9 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}$ :

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}$

Math	Appears 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}$

Infinite sum of nkxnn^kx^nnkxn

Comments

Infinite sum of $n^kx^n$