arithmetic - Possible pattern on sum of first $n$ $l$-th powers.

While discussing on some question with fleablood, we questioned ourselves on a possible pattern for the following sequence:
$$F_n(l):=\sum_{k=1}^n k^l$$

Using Wolframalpha (and well-knows results) we have
$$\begin{align*} F_n(1)&=\frac{n(n+1)}{2}\\ F_n(2)&=\frac{n(n+1)(2n+1)}{6}\\ F_n(3)&=F_n(1)^2\\ F_n(4)&=\frac{3n^2+3n-1}{5}F_n(2)\\ F_n(5)&=\frac{2n^2+2n-1}{3}F_n(3)\\ F_n(6)& = \frac{3n^4+6n^3-3n+1}{7}F_n(2) \end{align*}$$
Moreover using this question we (can) have

$$\sum_{i=1}^ni(i+1)(i+2)\dots(i+k-1)=\frac1{k+1}n(n+1)(n+2)\dots(n+k).$$
Is there a sequence to be spotted?

Note: This is sort of a challenge question, I see that I haven't put too much effort into it yet, but I found the question interesting nonetheless and thus wanted to share it with you.

Answer

Thanks to Vaughn Climenhaga and Mariano Suárez-Alvarez, I give you the interesting summation and picture

$$\underbrace{\sum_{k_1=1}^r\sum_{k_2=1}^{k_1}\sum_{k_3=1}^{k_2}\dots\sum_{k_{n-1}=1}^{k_{n-2}}\sum_{k_n=1}^{k_{n-1}}}_n1=\frac{(r+n-1)!}{n!(r-1)!}\tag1$$

visual proof for $n=2$:

example usage:

$$F_n(0)=\sum_{k=1}^n1=\frac{n!}{1!(n-1)!}=n$$

$$F_n(1)=\sum_{k=1}^nk=\sum_{k_1=1}^n\sum_{k_2=1}^{k_1}1=\frac{(n+1)!}{2!(n-1)!}=\frac{n(n+1)}2$$

$$F_n(2)=\sum_{k=1}^nk^2=\sum_{k=1}^n2\frac{k(k+1)}2-k=\sum_{k=1}^n2F_k(1)-F_k(0)=2\frac{(n+2)!}{3!(n-1)!}-\frac{(n+1)!}{2!(n-1)!}$$

$$F_n(2)=\frac{n(n+1)(n+2)}3-\frac{n(n+1)}2$$

And of course, if you wish, you can check it by expanding and combining the fractions.

Note that I used a relation findable from $(1)$:

$$\sum_{r=1}^n\frac{(r+k-1)!}{k!(r-1)!}=\frac{(n+k)!}{n!k!}$$

(which results in the last summation you have posted with a small amount of manipulation and expansion)

---

Secondly, we have Faulhaber's formula:

$$\sum_{k=1}^nk^l=\frac1{l+1}\sum_{j=0}^l(-1)^j\binom{l+1}jB_jn^{l+1-j}\tag2$$

which is the expansion of the summation into a polynomial of $n$, where $B_n$ is the $n$th Bernoulli number.

For example:

$$\sum_{k=1}^nk^2=\frac13\left(B_0n^3-3B_1n^2+3B_2n^1\right)=\frac13\left(n^3+\frac32n^2+\frac12n\right)$$

---

Also note that $(1)$ can be thought of as numbers going down/diagonally in a straight line on Pascal's triangle. Naturally, the first column is $1$. In the next, it is the sum of $1$ repeatedly. Then the next column is the sum of the previous, etc., etc. If you don't know why, recall how to draw Pascal's triangle.

Another interesting thing is that the resulting polynomial always has a factor of $n(n+1)$ for $l>0$, since by recursively working our way to $n=0$ and $n=-1$, $F_n(l)=0$, making them roots for the polynomial

---

Trivially related things include the use of such series in a modular arithmetic problem:

Take an integer number $N$. Square it. Now divide it by $3$ and take the remainder. Can you find an integer $N$ such that the remainder will be $2$?

HINT: see if you can figure out a neat representation for the square of a number to see if it is divisible by $3$. It's my favorite way of 'solving' the problem.

---

EDIT (9/13/2016)

furthermore, there is a relationship to geometric sums:

$$\sum_{k=1}^nr^k=\frac{r^{n+1}-r}{r-1}$$

for $r=1$, this simplifies down to $F_n(0)$, which is see-able if we evaluate the limit as $r\to1$ using L'Hospital's rule.

Also,

$$\frac{d}{dr}\sum_{k=1}^nr^k=\sum_{k=1}^nkr^{k-1}$$

which agrees with $F_n(1)$ for $r\to1$

$$\implies\frac{d}{dr}\frac{r^{n+1}-r}{r-1}=\frac{((n+1)r^n-1)(r-1)-r^{n+1}+r}{(r-1)^2}=\frac{nr^{n+1}-(n+1)r^n+1}{(r-1)^2}$$

which evaluates to $F_n(1)$ as $r\to1$.

More generally,

$$F_n(l)=\lim_{r\to1}\underbrace{\frac{d}{dr}r\cdot\frac{d}{dr}r\cdot\frac{d}{dr}r\cdot\dots\frac{d}{dr}r\cdot\frac{d}{dr}}_{l\ \frac{d}{dr}'s}\frac{r^{n+1}-r}{r-1}\tag3$$

which evaluates $F_n(l)$ for arbitrary $n$ and $l\in\mathbb N$, as opposed to the original definition of $F_n(l)$ being only calculateable for $n\in\mathbb Z$ and arbitrary $l$ (though not in closed form).

---

Very similarly,

$$F_n(-l)=\underbrace{\int_0^n\frac1{a_{k-1}}\int_0^{a_{k-1}}\frac1{a_{k-2}}\int_0^{a_{k-2}}\dots\int_0^{a_1}}_{l\text{ integrals}}\frac{r^n-1}{r-1}drda_1da_2da_3\dots da_{k-1}$$

Will leave it up to you to show why this is, as it is very similar to the above.

---

If you use the following, thanks to Jack D'Aurizio:

$$k^{-l}=\frac{1}{(l-1)!}\int_{0}^{1}t^{k-1}\left(-\log t\right)^{l-1}dt$$

(which was from the definition of the Gamma function) then for arbitrary negative values of $l$ and arbitrary values of $n$,

$$F_n(l)=\frac1{\Gamma(l)}\int_0^1\frac{r^n-1}{r-1}(-\log r)^{-1-l}dr\tag4$$

---

So, assuming we keep $n,l\in\mathbb R$, you can use some combinations of the above to calculate $F_n(l)$ for any value of $n,l$, whole, negative, fractional, any values will be calculate-able. The only case I have not dealt with is $l>0$ and arbitrary $n$. I'm unsure of what to do in that case, but I'm sure I'll think of something.

---

Note that $F_1(l)=1$, and so if $F_n(l)$ could be expanded into a polynomial in $n$, then the sum of the coefficients (even if it were a power series, which it seems to be analytic) must be $1$.

$$F_n(l)=\sum_{k=0}^\infty a_kn^{l+1-k}$$

$$F_1(l)=1=\sum_{k=0}^\infty a_k$$

Also, another remark is that the leading coefficient is going to be $\frac1{l+1}$, since

$$F_n(l)=\int_1^nr^ldr+O(n^l)=\frac1{l+1}n^{l+1}+O(n^l)$$

Knowing that it will always be 'divisible' by $n(n+1)$ may be helpful in some way, but I cannot see it would be for the general value of $n,l$ since you can always carry out long division indefinitely.

---

As a last remark

$$\lim_{n\to\infty}F_n(l)=\zeta(-l)\tag{$\Re(l)<-1$}$$

where $\zeta(z)$ is the Riemann zeta function.

---

If we define some $f^n(x)$ as

1. $f^n(x)=f^n(x-1)+x^n$




2. $f^n(1)=1$

then for $x\in\mathbb N$, $f^n(x)=F_x(n)$.

See then that:

$$f^n(x)=f^n(x-1)+x^n$$

$$g^n(x)=g^n(x-1)+nx^{n-1}\tag{$g(x)=\frac d{dx}f(x)$}$$

$$g^n(x)=g^n(x-2)+n\left[(x-1)^{n-1}+x^{n-1}\right]\\\vdots\\ g^n(x)=g^n(0)+n\left[1^{n-1}+2^{n-1}+\dots+(x-1)^{n-1}+x^{n-1}\right]\\=g^n(0)+nf^{n-1}(x)$$

$$f^n(x)-\require{cancel}\cancelto0{f^n(0)}=\int_0^xg^n(t)dt\\=g^n(0)x+n\int_0^xf^{n-1}(t)dt$$

which may very well be a recursive relationship you want.