Infinite sum of nkxnn^kx^n

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

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

xS=x+x2+x3+=n=1xn=(n=1xn)+x0x0=(n=0xn)1=S1xS=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=S1xS=S-1

1=SSx1=S-Sx

1=(1x)S1=(1-x)S

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

This answers the question for k=0k=0, to solve this for other kk, 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):

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

ddx[11x]=ddx[n=0xn]\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]

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

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

x(1x)2=n=0nxn\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):

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

Then I get:

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

Note to get the answer for k=2k=2, I can do the derivative of both sides, then multiply by xx, and then apply partial fractions, but then I can do for k=3k=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=pk=p, there is a sequence of Ap,nA_{p,n} as the coefficients of 1(1x)n\frac{1}{(1-x)^n} such that:

k=1p+1Ap,k(1x)k=k=0kpxk\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:

k=1p+1kAp,k(1x)k+1=k=0kp+1xk1\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 xx:

k=1p+1kAp,kx(1x)k+1=k=0kp+1xk\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:

k=1p+1kAp,k(1x)k+1k=1p+1kAp,k(1x)k=k=0kp+1xk\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+1k=p+1, therefore I can say that this is equal to the sum of 1(1x)k\frac{1}{(1-x)^k}, with the appropriate coefficients Ap+1,kA_{p+1,k}, also, I will take out the last and first coefficients because they don't have pairs, with that I can say:

kAp,p+1(1x)p+2+k=2p+1((k1)Ap,k1(1x)kkAp,k(1x)k)Ap,11x=k=0kp+1xk=k=1p+2Ap+1,k(1x)k\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:

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

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

Ap+1,k=(k1)Ap,k1kAp,kA_{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):

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

Ap,1=(1)nA_{p,1}=(-1)^n

Ap,p=(p+1)!2A_{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
2 years, 3 months ago

No vote yet
1 vote

  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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

k=0knxk=k=0nk!  S(n+1,k+1)(x1x)k+1 \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 - 2 years, 2 months ago

Log in to reply

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

Mark Hennings - 2 years, 2 months ago

Log in to reply

Apparently k=1knxk=k=1n+1(1)n+k+1S(n+1,k)(k1)!(1x)k.\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 - 2 years, 2 months ago

Log in to reply

And here is a proof by induction: It is easy to verify that the formula holds for n=1n = 1, so assume that it holds for some positive integer nn, i.e. k=1knxk=k=1n+1(1)n+k+1S(n+1,k)(k1)!(1x)k.\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 k=1kn+1xk1=k=1n+1(1)n+k+1S(n+1,k)k!(1x)k+1,\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 k=1kn+1xk=k=1n+1(1)n+k+1S(n+1,k)k!x(1x)k+1.\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 x(1x)k+1=(x1)+1(1x)k+1=1(1x)k+11(1x)k,\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 k=1n+1(1)n+k+1S(n+1,k)k!x(1x)k+1=k=1n+1((1)n+k+1S(n+1,k)k!(1x)k+1(1)n+k+1S(n+1,k)k!(1x)k)=(1)n+11x+k=2n+1((1)n+kS(n+1,k1)(k1)!(1x)k(1)n+k+1S(n+1,k)k!(1x)k)+(n+1)!(1x)n+2=(1)n+11x+k=2n+1(1)n+k(k1)!(1x)k[S(n+1,k1)+kS(n+1,k)]+(n+1)!(1x)n+2=(1)n+11x+k=2n+1(1)n+kS(n+2,k)(k1)!(1x)k+(n+1)!(1x)n+2=k=1n+2(1)n+kS(n+2,k)(k1)!(1x)k. \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.

Jon Haussmann - 2 years, 2 months ago

Log in to reply

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 - 2 years, 2 months ago

Log in to reply

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

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

dp1dp1x[11x]=dp1dp1x[n=0xn]\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 ]

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

(p1)!(1x)p=n=0n(p)xn\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 Cp,nC_{p,n} such that:

k=1pCp,kx(k)=xp\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 Ap,n=(n1)!Cp,nA_{p,n}=(n-1)!C_{p,n}

Matheus Jahnke - 2 years, 2 months ago

Log in to reply

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

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

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

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

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

Now, trying to find the recurrence around Cp,nC_{p,n}:

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

Multiplying everything by xx:

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

Using the recurrence of the Rising Factorial:

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

k=1pCp,kx(k+1)k=1pCp,kkx(k)=xp+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)Cp,p+k=2px(k)(Cp,k1kCp,k)x(k)Cp,1=xp+1x^{(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:

Cp+1,p+1=Cp,pC_{p+1,p+1}=C_{p,p}

Cp+1,k=Cp,k1kCp,kC_{p+1, k}=C_{p,k-1}-kC_{p,k}

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

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

Cn,n=1C_{n,n}=1

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

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

Matheus Jahnke - 2 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...