During the course of another math.se question (What's the probability of completing the illustrated "binomial walk" without ever visiting a node above the baseline?), the following generalization of $\sum_{i=1}^n i = \frac{n(n+1)}2$ tangentially (not directly related to that discussion) came up. Moreover, it also satisfies several "magic formulas" shown below (but not posted earlier) that suggested to me maybe it's already some well-known "thing" (i.e., "somebody's polynomial" or something). If so, anybody know what it's called, and can point me to a more complete development? Here's the definition, and then those formulas that follow from it...
Define $$ \left. \begin{array}{cclcl} H^1_n & = & & & 1 \mbox{ for all $n$} \\ H^2_n & = & \sum_{i=1}^n H^1_i & = & n \\ H^3_n & = & \sum_{i=1}^n H^2_i & = & \frac{n(n+1)}{2!} \mbox{ (the usual)}\\ H^4_n & = & \sum_{i=1}^n H^3_i & \stackrel{?}{=} & \underbrace{an^3+bn^2+cn}_{ \mbox{solve for $a,b,c$...}} \\ & & & = & \frac{1}{6}n^3 + \frac{1}{2}n^2 + \frac{1}{3}n \\ & & & = & \frac{n(n+1)(n+2)}{3!} \\ \end{array}\right\} \begin{array}{r} i.e., H^m_n \stackrel{\mbox{def}}{=} \sum_{i=1}^n H^{m-1}_i, \mbox{with } H^1_n=1.\\ \mbox{And since } H^m_{n-1}=\sum_{i=1}^{n-1} H^{m-1}_i,\\ \mbox{note that } H^m_n=H^m_{n-1}+H^{m-1}_n \mbox{ too.} \end{array} $$
And by examination we infer the general expression
$\begin{array}{ccl}
H^m_n & = & \frac{1}{(m-1)!} \prod_{k=1}^{m-1} (n+k-1) \\
& = & \frac{(n+m-2)!}{(m-1)!(n-1)!} \\
& & \mbox{which simplifies to} \\
& = & \binom{n+m-2}{m-1} = \binom{n+m-2}{n-1} \\
\end{array}$
And also note that $H^m_n=H^n_m$.
The two "magic formulas" that I numerically tested beyond any reasonable doubt (but haven't been able to derive) are,
$$H^{m+2}_m - \sum_{k=1}^{m-1} kH^{m+1-k}_m = m \mbox{, for any } m$$
and
$$\frac{1}{m}H^{m+2}_m = \frac{1}{m}\sum_{k=1}^m kH^{m+1-k}_m
= \frac{1}{m-1}\sum_{k=1}^{m-1} k(k+1)H^{m-k}_{m-1}$$
But note that the more general progression suggested by the second formula
fails.
** Edit **
-------------------
Re @mrtaurho's remark about verification, I numerically generated the table illustrated below, and had the computer compare those directly-calculated values against the binomial coefficient expression. Everything's copacetic (and the computer checked many, many more values than illustrated on the table)...
$\begin{array}{ccccccccccccc}
n&H^1_n&H^2_n&H^3_n&H^4_n&H^5_n&H^6_n&H^7_n&H^8_n&
H^9_n&H^{10}_n&H^{11}_n&H^{12}_n \\
1&{\bf 1}&1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
2&1&{\bf 2} & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10& 11& 12 \\
3&1&3 &{\bf 6}& 10& 15& 21& 28& 36& 45& 55& 66& 78 \\
4&1&4 & 10&{\bf 20}& 35& 56& 84&120&165&220&286&364 \\
5&1&5 & 15& 35&{\bf 70}&126&210&330&495&715&1001&1365 \\
6&1&6 & 21& 56&126&{\bf 252}&462&792&1287&2002&3003&4368 \\
7&1&7 & 28& 84&210&462&{\bf 924}&1716&3003&5005&8008&12376 \\
8&1&8 & 36&120&330&792&1716&{\bf 3432}&6435&11440&19448&31824 \\
9&1&9 & 45&165&495&1287&3003&6435&{\bf 12870}&24310&43758&75582 \\
10&1&10& 55&220&715&2002&5005&11440&24310&{\bf 48620}&92378&167960 \\
11&1&11& 66&286&1001&3003&8008&19448&43758&92378&{\bf 184756}&352716 \\
12&1&12& 78&364&1365&4368&12376&31824&75582&167960&352716&{\bf 705432}\\
13&1&13& 91&455&1820&6188&18564&50388&125970&293930&646646&1352078\\
14&1&14&105&560&2380&8568&27132&77520&203490&497420&1144066&2496144\\
15&1&15&120&680&3060&11628&38760&116280&319770&817190&1961256&4457400\\
16&1&16&136&816&3876&15504&54264&170544&490314&1307504&3268760&7726160\\
\end{array}$
I really tried to play around with your two "magic formulas" but I did not found anything useful. Nevertheless I can prove your explicit formula for $H^m_n$ using a proof I did on a different post (which you can find here : Help on induction, couldn't make both side the same value). The relation there is
$$\sum_{k=1}^n k(k+1)~\cdots (k+p-1)~=~ \frac{n(n+1)\cdots (n+p)}{p+1}$$
which I will use later on. First of all we write $H_n^{m+1}$ in terms of $H_n^m$ with the equation you defined
$$H^{m+1}_n~=~\sum_{k=1}^n H_k^m $$
Now using your derived indentity
$$H_n^m~=~\binom{n+m-2}{m-1}~~\text{and respectively}~~H_n^{m+1}~=~\binom{n+m-1}{m}$$
we obtain
$$\begin{align} H^{m+1}_n~&=~\sum_{k=1}^n H_k^m\\ \binom{n+m-1}{m}~&=~\sum_{k=1}^n \binom{k+m-2}{m-1}\\ \frac{(n+m-1)!}{(n-1)!~m!}~&=~\sum_{k=1}^n \frac{(k+m-2)!}{(k-1)!~(m-1)!}\\ \frac{(n+m-1)!}{(n-1)!~m}~&=~\sum_{k=1}^n \frac{(k+m-2)!}{(k-1)!}\\ \frac{n(n+1)\cdots (n+m-1)}{m}~&=~\sum_{k=1}^n k(k+1)~\cdots (k+m-2) \end{align}$$
which equals my given equation by setting $m=p+1$.
Maybe you can go further from there on but atleast you got a proof as a verification for your solution by examination.
My try on the first "magic formula"
$$\begin{align} H_m^{m+2}-\sum_{k=1}^{m-1} k H_m^{m-k+1}~&=~m\\ H_m^{m+2}-\sum_{k=1}^{m-1} k H_m^{m-k+1}+mH_m^{1}-mH_m^{1}~&=~m\\ H_m^{m+2}-\sum_{k=1}^{m} k H_m^{m-k+1}+mH_m^1~&=~m\\ H_m^{m+2}-\sum_{k=1}^{m} k H_m^{m-k+1}+m\cdot (1)~&=~m\\ H_m^{m+2}~&=~\sum_{k=1}^{m} k H_m^{m-k+1}\\ \sum_{k=1}^m H_k^{m+1}~&=~\sum_{k=1}^{m} k H_m^{m-k+1} \end{align}$$
so therefore I guess it should be somehow possible to show
$$H_k^{m+1}~=~k H_m^{m-k+1}$$
But till now it leads me to nowhere