*This is a crosspost of a question I asked on Mathematics SE four months ago. Periodically bumping it and placing a bounty on it to attract more attention were to no avail. There are some comments underneath it by @darijgrinberg that I found useful, but the only conclusion in that discussion was that the proof really is confusing.*

I am having trouble with Lemma 2.3 in the paper "A combinatorial proof of the log-concavity of the numbers of permutations with $k$ runs" by Bóna and Ehrenborg, and I was hoping to get some help in clarifying how the proof works.

Let $n > 1$. We say that the permutation $p \in \mathfrak{S}_n$ has *$k$ alternating runs* (or just *$k$ runs*) if $p$ changes direction at $k-1$ points, that is, if there are $k$ values of $i \in \left\{2,3,\ldots,n-1\right\}$ such that either $p_{i-1} < p_i > p_{i+1}$ or $p_{i-1} > p_i < p_{i+1}$. Let $r(p)$ be the number of runs of $p$, and $$R_n(x) := \sum_{p \in \mathfrak{S}_n} x^{r(p)}.$$ The authors give a combinatorial proof of the fact that $-1$ is a root of $R_n(x)$ with multiplicity $m = \lfloor (n - 2) / 2\rfloor$ for all $n \geq 4$.

Let $1 \leq j \leq m+1$ and $p \in \mathfrak{S}_n$. We say that $p$ is *$j$-half-ascending* if the last $j$ disjoint pairs of elements in the sequence $p_1,p_2,\dotsc,p_n$ are ascending, that is, if $p_{n+1-2i} < p_{n+2-2i}$ for all $1 \leq i \leq j$. For a $(j+1)$-half-ascending permutation $p \in \mathfrak{S}_n$, define $r_j(p)$ to be the number of runs of the subsequence $p_1,p_2,\dotsc,p_{n-2j}$, and $s_j(p)$ to be the number of *descents* of the subsequence $p_{n-2j},p_{n-2j+1},\dotsc,p_n$. Define $t_j(p) := r_j(p) + s_j(p)$, and let $$R_{n,j}(x) := \sum_{p} x^{t_j(p)},$$ where the sum is taken over all the $(j+1)$-half-ascending permutations $p$ in $\mathfrak{S}_n$. (In the paper, the sum is apparently taken over all $p \in \mathfrak{S}_n$, but that is surely a typo because $t_j(p)$ does not make sense for all $p \in \mathfrak{S}_n$.)

Lemma 2.3.For all $n \geq 4$ and $1 \leq j \leq m$, we have $$\frac{R_n(x)}{2(x+1)^j} = R_{n,j}(x).$$

The proof goes by induction. For the base case, we first note that $p$ and $p^c$ (the *complement* of $p$) have the same number of runs, so that
$$
\frac{R_n(x)}{2} = \sum_{p : p_{n-3} < p_{n-2}} x^{r(p)}.
$$
Let $I$ be the involution on $\mathfrak{S}_n$ that swaps $p_{n-1}$ and $p_n$. One can check that for every $p \in S_n$ such that $p_{n-3} < p_{n-2}$, $r(p)$ and $r(I(p))$ differ by $1$ (it suffices to check this only for the permutations in $\mathfrak{S}_4$, since it is only the last $4$ terms in the sequence $p_1,\dotsc,p_n$ that are really relevant here). Let $q \equiv q(p)$ be that permutation in the set $\{ p, I(p) \}$ with smaller number of alternating runs. Then,
$$
\sum_{p : p_{n-3} < p_{n-2}} x^{r(p)} = \sum_{q(p)} \bigl(x^{r(q)} + x^{r(q)+1}\bigr) = (1+x) \sum_{q(p)} x^{r(q)}.
$$
Let $q' \equiv q'(p)$ be that permutation in the set $\{ p, I(p) \}$ which is $2$-half-ascending. Then, it turns out that $r(q) = t_1(q')$ (again, it suffices to only check this for the permutations in $\mathfrak{S}_4$). So,
$$
\sum_{q(p)} x^{r(q)} = \sum_{q'(p)} x^{t_1(q')} = R_{n,1}(x).
$$
Hence, $R_n(x)/2(1+x) = R_{n,1}(x)$, as required.

Now, this is what the authors say regarding the induction step:

Now suppose we know the statement for $j-1$ and prove it for $j$. As above, apply $I$ to the two rightmost entries of our permutations to get pairs as in the initial case, and apply the induction hypothesis to the leftmost $n-2$ elements. By the induction hypothesis, the string of the leftmost $n-2$ elements can be replaced by a $j$-half-ascending $n-2$-permutation, and the number of runs can be replaced by the $t_{j-1}$-parameter. In particular, $p_{n-3} < p_{n-2}$ will hold, and therefore we can verify that our statement holds in both cases ($p_{n-2} < p_{n-1}$ or $p_{n-2} > p_{n-1}$) exactly as we did in the proof of the initial case. . .

This is quite confusing to me; I cannot interpret this paragraph in a way to actually make the proof work. I would be happy to even just see how the inductive step works in the case $n = 6$.

### References

*Bóna, Miklós; Ehrenborg, Richard*,**A combinatorial proof of the log-concavity of the numbers of permutations with $k$ runs**, J. Comb. Theory, Ser. A 90, No. 2, 293-303 (2000). ZBL0951.05002.*Bóna, Miklós*,**Combinatorics of permutations**, Discrete Mathematics and its Applications. Boca Raton, FL: CRC Press (ISBN 978-1-4398-5051-0/hbk; 978-1-4398-5052-7/ebook). 458 p. (2012). ZBL1255.05001.