Setting. On page 270 of the great book Concrete Mathematics by Graham, Knuth and Patashnik, the second order Eulerian numbers $\langle\!\langle {n\atop k}\rangle\!\rangle$ with $n,k\in\mathbb{Z}$, $n \geq 0$ are defined recursively on page 270 by $\langle\!\langle {0\atop k}\rangle\!\rangle = \delta_{k,0}$ and
$$
\Big\langle\!\!\Big\langle {n\atop k}\Big\rangle\!\!\Big\rangle = (k+1)\Big\langle\!\!\Big\langle {n-1\atop k}\Big\rangle\!\!\Big\rangle + (2n – 1 – k)\Big\langle\!\!\Big\langle {n-1\atop k-1}\Big\rangle\!\!\Big\rangle.
$$
They form a triangle of the same shape as the Pascal triangle.
On page 271, they write (I've adjusted the text slightly):
Second-order Eulerian numbers are important chiefly because of their connection with Stirling numbers: We have, by induction on $n$,
$$\Big\{{n \atop n-k}\Big\} = \sum_i \Big\langle\!\!\Big\langle {k \atop i}\Big\rangle\!\!\Big\rangle \binom{n+k-1-i}{2k}$$
and
$$\Big[{n \atop n-k}\Big] = \sum_i \Big\langle\!\!\Big\langle {k \atop i}\Big\rangle\!\!\Big\rangle \binom{n+i}{2k}$$
for all integers $n \geq 0$.
The left hand sides denote Stirling numbers of second and first kind, respectively, aka Stirling subset and Stirling cycle numbers. The range of the summation signs can be assumed to be $i\in\{0,\ldots, k\}$, or for $n \neq 0$ even $i\in\{0,\ldots,k-1\}$, as in all other cases $\langle\!\langle {k\atop i}\rangle\!\rangle$ will be $0$.
Question. How is the indicated induction done explicitly?
I've tried it for a while, only using the recurrence relations
$$
\Big[{n\atop k}\Big] = (n-1)\Big[{n-1 \atop k}\Big] + \Big[{n-1 \atop k-1}\Big],\\
\Big\{{n\atop k}\Big\} = k\Big\{{n-1 \atop k}\Big\} + \Big\{{n-1 \atop k-1}\Big\},\\
\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}
$$
and the boundary values $\{{0 \atop k}\} = [{0 \atop k}] = ({0 \atop k}) = \delta_{k,0}$, but it gets messy and so far, I didn't succeed. But I feel it really should be doable.
Important. I'm only interested in proofs fitting the discussed spot of the book, preferably an inductive proof as indicated. Many identities for binomial coefficients and Stirling numbers are available, however no generating functions (they are introduced only in the following chapter of the book).
Also, please keep this restriction in mind when thinking about closing this question as a duplicate. (I didn't find one, but you never know. The closest I came across is this question.)
Best Answer
$\newcommand{\eulersec}[2]{\genfrac{\langle}{\rangle}{0pt}{}{#1}{#2}} \newcommand{\stirlingcyc}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} \newcommand{\stirlingset}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}$ In the meanwhile, I managed to do it. My problem was that I had attached the factor $(n-1)$ to the wrong summand in the recursion formula of the Stirling numbers.
Without such blunders, the inductive proof is almost straightforward, though a bit tedious. I will use single angle brackets for the second order Eulerian numbers, for easier TeXing.
By direct calculations, one checks the claimed equations for $k \leq 0$ and $n = 0$.
Induction for Stirling cycle numbers. For $k > 0$ and $n > 0$, we are going to show that the difference $$\sum_{i=0}^k \eulersec{k}{i} \binom{n+i}{2k} - \stirlingcyc{n}{n-k}$$ of the two sides of the claimed identity vanishes. By the recursion formula of the Stirling cycle numbers, it equals $$= \sum_{i=0}^k \eulersec{k}{i} \binom{n+i}{2k} - \stirlingcyc{n-1}{(n-1)-k} - (n-1)\stirlingcyc{n-1}{(n-1)-(k-1)}.$$ We apply the induction hypothesis to both Eulerian numbers and get $$\sum_{i=0}^k \eulersec{k}{i} \left(\binom{n+i}{2k}-\binom{n-1+i}{2k}\right) - (n-1) \sum_{i=0}^{k-1} \eulersec{k-1}{i} \binom{n-1+i}{2(k-1)}.$$ By the recursion formula for the binomial coefficients, \begin{multline*}= \sum_{i=0}^k \left((i+1) \eulersec{k-1}{i} + (2k-1-i)\eulersec{k-1}{i-1}\right) \binom{n-1+i}{2k-1} \\ - (n-1) \sum_{i=0}^{k-1} \eulersec{k-1}{i} \binom{n-1+i}{2k-2}. \end{multline*} Now we shift the summation index for the middle term by one. Using that $\eulersec{k-1}{-1} = \eulersec{k-1}{k}$, we rearrange the expression as $$= \sum_{i=0}^{k-1} \left((i+1)\binom{n-1+i}{2k-1} + (2k-2-i) \binom{n+i}{2k-1} - (n-1) \binom{n-1+i}{2k-2}\right) \eulersec{k-1}{i}.$$ This expression vanishes, since using the recursion formula for the binomial coefficients \begin{align*} & (i+1)\binom{n-1+i}{2k-1} + (2k-2-i) \binom{n+i}{2k-1} - (n-1) \binom{n-1+i}{2k-2} \\ & = (i+1)\binom{n-1+i}{2k-1} + (2k-2-i)\left(\binom{n+i-1}{2k-1} + \binom{n+i-1}{2k-2}\right) + (n-1) \binom{n-1+i}{2k-2} \\ & = (2k-1)\binom{n-1+i}{2k-1} - (n+i-2k-3)\binom{n+i}{2k-2} \\ & = 0, \end{align*} where for the last step the rule \begin{equation}\label{eq:helper} K\binom{N}{K} = (N-K+1)\binom{N}{K-1}\tag{$\ast$} \end{equation} was used.
Induction for Stirling subset numbers. The induction for the other formula is done in a similar way. We again start with the difference $$\sum_{i=0}^k \eulersec{k}{i} \binom{n+k-1-i}{2k} - \stirlingset{n}{n-k}.$$ By the recursion formula for the Stirling subset numbers, $$= \sum_{i=0}^k \eulersec{k}{i} \binom{n+k-1-i}{2k} - \stirlingset{n-1}{(n-1)-k} - (n-k)\stirlingset{n-1}{(n-1)-(k-1)}.$$ Applying the induction hypothesis to the two Eulerian numbers, $$= \sum_{i=0}^k \eulersec{k}{i} \left(\binom{n+k-1-i}{2k}-\binom{n+k-2-i}{2k}\right) - (n-k) \sum_{i=0}^{k-1} \eulersec{k-1}{i} \binom{n+k-3+i}{2(k-1)}.$$ Applying the recursion formula for the binomial coefficients, \begin{multline*} \sum_{i=0}^k \left((i+1) \eulersec{k-1}{i} + (2k-1-i)\eulersec{k-1}{i-1}\right) \binom{n+k-2-i}{2k-1} \\ - (n-k) \sum_{i=0}^{k-1} \eulersec{k-1}{i} \binom{n+k-3-i}{2k-2}. \end{multline*} Now we shift the summation index for the middle term by one. Using that $\eulersec{k-1}{-1} = \eulersec{k-1}{k}$, we rearrange the expression as \begin{multline*}= \sum_{i=0}^{k-1} \left((i+1)\binom{n+k-2-i}{2k-1} + (2k-2-i) \binom{n+k-3-i}{2k-1}\right. \\ \left. - (n-k) \binom{n+k-3-i}{2k-2}\right) \eulersec{k-1}{i}\end{multline*} This expression vanishes, since using the recursion formula for the binomial coefficients \begin{align*} & (i+1)\binom{n+k-2-i}{2k-1} + (2k-2-i) \binom{n+k-3-i}{2k-1}- (n-k) \binom{n+k-3-i}{2k-2} \\ & = (i+1)\left(\binom{n+k-3-i}{2k-2} + \binom{n+k-3-i}{2k-1}\right) + (2k-2-i) \binom{n+k-3-i}{2k-1}- (n-k) \binom{n+k-3-i}{2k-2} \\ & = (2k-1)\binom{n+k-3-i}{2k-1} - (n-k-i-1)\binom{n+k-3-i}{2k-2} \\ & = 0, \end{align*} where in the last step again fomula \eqref{eq:helper} was used.