Possible pattern on sum of first $n$ $l$-th powers.
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
$f^n(x)=f^n(x-1)+x^n$
$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.
As Lonidard has pointed out, expressions for $F_n(l)$ in terms of $F_n(l'), l'<l$ can be obtained by means of the binomial theorem and summing the terms of a telescoping series.
Here I give an alternative form, in terms of the triangular numbers
$$T(i)=F_i(1)=\dfrac{i(i+1)}2$$
and, for even $l$, the square-based pyramidal numbers
$$P(i)=F_i(2)=\dfrac{i(i+1)(2i+1)}6.$$
First, for odd $l=2j-1$: Let \begin{align*} A(i)&=[2T(i)]^j\\ &=[i(i+1)]^j\\ &=i^j(i+1)^j\\ \Rightarrow A(i-1)&=i^j(i-1)^j\\ \Rightarrow A(i)-A(i-1)&=i^j[(i+1)^j-(i-1)^j]\\ &=i^j\left[\sum_{r=0}^j \binom j r i^{j-r}-\sum_{r=0}^j(-1)^r\binom{j}r i^{j-r}\right]\\ &=2 \sum_{\substack{r=1\\r \textrm{ odd}}}^j \binom j r i^{2j-r}\\ \Rightarrow [2T(n)]^j&=2 \sum_{\substack{r=1\\r \textrm{ odd}}}^j \binom j r F(2j-r)\tag{telescoping}\\ \Rightarrow 2^{j-1}T^j&=\sum_{\substack{r=1\\r \textrm{ odd}}}^j \binom j r F(2j-r)\\ &=jF(2j-1)+\sum_{\substack{r=3\\r \textrm{ odd}}}^j \binom j r F(2j-r)\\ \Rightarrow F(2j-1)&=\left[2^{j-1}T^j-\sum_{\substack{r=3\\r \textrm{ odd}}}^j \binom j r F(2j-r)\right]/j\\ \Rightarrow F(l)&=\left[2^{j-1}T^j-\sum_{\substack{r=3\\r \textrm{ odd}}}^j \binom j r F(l-r+1)\right]/j \end{align*} where $l=2j-1$. This gives expressions for the $F(l)$ for $l$ odd.
A similar technique works for $l$ even, though it is more complicated. First, a result which will help with the somewhat strange way that binomial coefficients need to be paired:
Lemma. $$j\left[\binom{j}r+\binom{j-1}r\right]=(2j-r)\binom{j}r.$$
Proof. \begin{align*} j\left[\binom{j}r+\binom{j-1}r\right]&=\dfrac{jj!}{r!(j-r)!}+\dfrac{j(j-1)!}{r!(j-r-1)!}\\ &=[j+(j-r)]\dfrac{j(j-1)!}{r!(j-r)!}\\ &=(2j-r)\binom{j}r. \end{align*}
Let $P(i)=F_i(2)=i(i+1)(2i+1)/6$ and \begin{align*} A(i)&=2^{j-2}3jP(i)T(i)^{j-2}\\ &=3j[2T(i)]^{j-2}P(i)\\ &=j[i(i+1)]^{j-2}i(i+1)(2i+1)/2\\ &=ji^{j-2}(i+1)^{j-2}i(i+1)(2i+1)/2\\ &=ji^{j-1}(i+1)^{j-1}(2i+1)/2\\ \Rightarrow A(i-1)&=j(i-1)^{j-1}i^{j-1}(2i-1)/2\\ \Rightarrow A(i)-A(i-1)&=ji^{j-1}\left[(2i+1)(i+1)^{j-1}-(2i-1)(i-1)^{j-1}\right]/2\\ &=ji^{j-1}\left[i(i+1)^{j-1}+(i+1)(i+1)^{j-1}-i(i-1)^{j-1}-(i-1)(i-1)^{j-1}\right]/2\\ &=ji^{j-1}\left[i(i+1)^{j-1}+(i+1)^j-i(i-1)^{j-1}-(i-1)^j\right]/2\\ &=ji^{j-1}\left[i(i+1)^{j-1}-i(i-1)^{j-1}+(i+1)^j-(i-1)^j\right]/2\\ &=ji^j\left[(i+1)^{j-1}-(i-1)^{j-1}\right]/2+ji^{j-1}\left[(i+1)^j-(i-1)^j\right]/2\\ &=ji^j\left[\sum_{r=0}^{j-1}\binom{j-1}r i^{j-r-1}-\sum_{r=0}^{j-1}(-1)^r\binom{j-1}r i^{j-r-1}\right]/2\,+\\ &\qquad+ji^{j-1}\left[\sum_{r=0}^j\binom{j}r i^{j-r}-\sum_{r=0}^j (-1)^r\binom{j}r i^{j-r}\right]/2\\ &=ji^j\sum_{\substack{r=1\\r \textrm{ odd}}}^{j-1}\binom{j-1}r i^{j-r-1}+ji^{j-1}\sum_{\substack{r=1\\r \textrm{ odd}}}^j\binom{j}r i^{j-r}\\ &=\sum_{\substack{r=1\\r \textrm{ odd}}}^j j\left[\binom{j-1}r+\binom{j}r\right]i^{2j-r-1}\\ &=\sum_{\substack{r=1\\r \textrm{ odd}}}^j (2j-r) \binom j{r} i^{2j-r-1}\tag{by the lemma}\\ \Rightarrow A(n)&=\sum_{\substack{r=1\\r \textrm{ odd}}}^j (2j-r) \binom j{r} F(2j-r-1)\tag{telescoping}\\ \Rightarrow 2^{j-2}3jPT^{j-2}&=j(2j-1)F(2j-2)+ \sum_{\substack{r=3\\r \textrm{ odd}}}^{j} (2j-r) \binom j{r} F(2j-r-1)\\ \Rightarrow j(2j-1)F(2j-2)&=2^{j-2}3jPT^{j-2} - \sum_{\substack{r=3\\r \textrm{ odd}}}^{j} (2j-r) \binom j{r} F(2j-r-1)\\ \Rightarrow F(2j-2)&=\left[2^{j-2}3jPT^{j-2} - \sum_{\substack{r=3\\r \textrm{ odd}}}^{j} (2j-r) \binom j{r} F(2j-r-1)\right]/j(2j-1)\\ \Rightarrow F(l)&=\left[2^{j-2}3jPT^{j-2} - \sum_{\substack{r=3\\r \textrm{ odd}}}^{j} (l-r+2) \binom j{r} F(l-r+1)\right]/{j(l+1)}, \end{align*} where $l=2j-2$.
Here are some explicit examples, reduced to their lowest terms and with some further simplification where possible. You might also find that [Knuth] has some useful information.
\begin{align*} F(3) &= T^2\\ F(4) &= (6PT-F(2))/5=P(6T-1)/5\\ F(5) &= (4T^3-F(3))/3 = T^2(4T-1)/3\\ F(6) &= (12PT^2-5F(4))/7\\ F(7) &= 2T^4-F(5)\\ F(8) &= (24PT^3-14F(6)+F(4))/9\\ F(9) &= (16T^5-10F(7)-F(5))/5\\ &= (16T^5-F(5))/5-2F(7)\\ F(10) &= (48PT^4-30F(8)-7F(6))/11\\ F(11) &= (16T^6-10F(9)-3F(7))/3\\ &= (16T^6-10F(9))/3-F(7)\\ F(12) &= (96PT^5-55F(10)-27F(8)-F(6))/13\\ F(13) &= (64T^7-35F(11)-21F(9)-F(7))/7\\ &= (64T^7-F(7))/7 - 5 F(11) - 3 F(9)\\ F(14) &= (192PT^6-91F(12)-77F(10)-9F(8))/15\\ F(15) &= 16T^8-7F(13)-7F(11)-F(9) \\ &= 16T^8-7(F(13)+F(11))-F(9)\\ F(16) &= (384PT^7-140F(14)-182F(12)-44F(10)-F(8))/17\\ F(17) &= (256T^9-84F(15)-126F(13)-36F(11)-F(9))/9\\ &= (256T^9-84F(15)-F(9))/9-14F(13)-4F(11)\\ F(18) &= (768PT^8-204F(16)-378F(14)-156F(12)-11F(10))/19\\ F(19) &= (256T^{10}-60F(17)-126F(15)-60F(13)-5F(11))/5\\ &= (256T^{10}-126F(15))/5-12(F(17)+F(13))-F(11)\\ F(20) &= (1536PT^9-285F(18)-714F(16)-450F(14)-65F(12)-F(10))/21\\ F(21) &= (1024T^{11}-165F(19)-462F(17)-330F(15)-55F(13)-F(11))/11\\ &= (1024T^{11}-F(11))/11-15F(19)-42F(17)-30F(15)-5F(13)\\ F(22) &= (3072PT^{10}-385F(20)-1254F(18)-1122F(16)-275F(14)-13F(12))/23\\ F(23) &= (512T^{12}-55F(21)-198F(19)-198F(17)-55F(15)-3F(13))/3\\ &= (512T^{12}-55(F(21)+F(15)))/3-66(F(19)+F(17))-F(13)\\ F(24) &= (6144PT^{11}-506F(22)-2079F(20)-2508F(18)-935F(16)-90F(14)-F(12))/25\\ F(25) &= (4096T^{13}-286F(23)-1287F(21)-1716F(19)-715F(17)-78F(15)-F(13))/13\\ &= (4096T^{13}-F(13))/13-22F(23)-99F(21)-132F(19)-55F(17)-6F(15)\\ F(26) &= (12288PT^{12}-650F(24)-3289F(22)-5148F(20)-2717F(18)-442F(16)-15F(14))/27\\ F(27) &= (4096T^{14}-182F(25)-1001F(23)-1716F(21)-1001F(19)-182F(17)-7F(15))/7\\ &= (4096T^{14}-1716F(21))/7-26(F(25)+F(17))-143(F(23)+F(19))-F(15)\\ F(28) &= (24576PT^{13}-819F(26)-5005F(24)-9867F(22)-7007F(20)-1729F(18)-119F(16)-F(14))/29\\ F(29) &= (16384T^{15}-455F(27)-3003F(25)-6435F(23)-5005F(21)-1365F(19)-105F(17)-F(15))/15\\ &= (16384T^{15}-455F(27)-3003F(25)-5005F(21)-F(15))/15-429F(23)-91F(19)-7F(17)\\ F(30) &= (49152PT^{14}-1015F(28)-7371F(26)-17875F(24)-16445F(22)-5733F(20)-665F(18)-17F(16))/31\\ F(31) &= 2048T^{16}-35F(29)-273F(27)-715F(25)-715F(23)-273F(21)-35F(19)-F(17)\\ &= 2048T^{16}-35(F(29)+F(19))-273(F(27)+F(21))-715(F(25)+F(23))-F(17) \end{align*}
[Knuth] Donald Knuth. Johann Faulhaber and sums of powers. Mathematics of Computation 61, no.203 (Jul 1993), p.277-294.
Introduction
The following is not answer, but more of an observation about the problem: one can express the sum $F_n(m)$ as a shifted linear combination of $F_n(1),\ldots, F_n(m-1)$. This allows the computation of $F_n(m)$ by hand for small $m$, and through the use of computational software for higher values of $m$. I am by no means an expert on the subject and found the following while fiddling around and trying to find a closed form for $F_n(m)$ for fun some time ago.
Proving the claim
Let us call $$F_n(m):=\sum_{i=1}^ni^m$$ We start by observing that since $$\sum_{i=1}^n\left ((i+1)^{m+1}-i^{m+1} \right)$$ is telescopic, one has $$\sum_{i=1}^n\left ((i+1)^{m+1}-i^{m+1} \right)=(n+1)^{m+1}-1$$ Expanding the power on the left, we obtain $$\begin{align}{} (n+1)^{m+1}-1= &\sum_{i=1}^n\left (\sum_{j=0}^{m+1}\binom{m+1}{j}i^j-i^{m+1} \right) \\ =&\sum_{i=1}^n\sum_{j=0}^{m}\binom{m+1}{j}i^j \\ =&\sum_{j=0}^{m}\binom{m+1}{j}\sum_{i=1}^ni^j \\ =& n+ (m+1)\sum_{i=1}^n i+\ldots+(m+1)\sum_{i=1}^{n}i^m \end{align}$$ From here, we can express $F_n(m)$ as $$F_n(m)=\frac{1}{m+1}\left((n+1)^{m+1}-1-\sum_{j=0}^{m-1}\binom{m+1}{j}\ F_n(j) \right )$$
Checking the results
By observing that $$F_n(0)=\sum_{i=1}^n1=n$$ we can obtain the known formulas
$$\begin{align} F_n(1)= &\frac{1}{2}\left ((n+1)^2-1-n \right )\\=&\color{red}{\frac{n(n+1)}{2}} \\ F_n(2) =&\frac{1}{3}\left ((n+1)^2-1-n-3\frac{n(n+1)}{2} \right )\\ =&\color{red}{\frac{n(n+1)(2n+1)}{6}} & \end{align}$$
Brutally implementing these formulas in Mathematica I could compute the first $20$ $ F_n(m)$ in about $43$ seconds. Continuing your list one has $$F_n(7)=\frac{1}{24} \left(3 n^8+12 n^7+14 n^6-7 n^4+2 n^2\right)$$ $$F_n(8)=\frac{1}{90} n \left(n^2 \left(\left(5 n^2 (n (2 n+9)+12)-42\right) n^2+20\right)-3\right)$$ $$F_n(9)=\frac{1}{20} n^2 \left(n^2 \left(\left(n^2 (2 n (n+5)+15)-14\right) n^2+10\right)-3\right)$$ $$F_n(10)=\frac{1}{66} n \left(6 n^{10}+33 n^9+55 n^8-66 n^6+66 n^4-33 n^2+5\right)$$ $$F_n(11)=\frac{1}{24} n^2 \left(\left(n^2 \left(\left(2 n^2 (n (n+6)+11)-33\right) n^2+44\right)-33\right) n^2+10\right)$$ $$F_n(12)=\frac{n^{13}}{13}+\frac{n^{12}}{2}+n^{11}-\frac{11 n^9}{6}+\frac{22 n^7}{7}-\frac{33 n^5}{10}+\frac{5 n^3}{3}-\frac{691 n}{2730}$$ It doesn't look really good; from this point on the formulas get pretty ugly.
A computational note: the computation of $ F_{n-1}(m)$ is quite easier, yielding $$ F_{n-1}(m)=\frac{1}{m+1}\left(n^{m+1}-1-\sum_{j=0}^{m-1}\binom{m+1}{j} F_{n-1}(j) \right )$$ and one can connect these two formulas from the definition of $F_n(m)$: $$F_n(m)=\frac{1}{m+1}\left(n^{m+1}-1-\sum_{j=0}^{m-1}\binom{m+1}{j}\ F_{n-1}(j) \right )+n^m$$