I am reading the book Combinatorics of Permutations (2nd edition) by Miklós Bóna, and in $\S$1.2 Alternating Runs, he states and proves a lemma on page 29 whose proof I do not fully understand.
Assume $n > 1$. Let $p := p_1 p_2 \dotsm p_n$ be a permutation in $S_n$. We say that $p$ changes direction at $i \in \left\{2,3,\ldots,n-1\right\}$ if either $p_{i-1} < p_i > p_{i+1}$ or $p_{i-1} > p_i < p_{i+1}$. We say that $p$ has $k$ alternating runs if $p$ changes direction at $k-1$ points. Let $r(p)$ denote the number of alternating runs of $p$.
Let $G(n,k) := \lvert\{ p \in S_n : r(p) = k\}\rvert$, that is, $G(n,k)$ equals the number of permutations in $S_n$ having $k$ alternating runs. Consider the generating function $$ G_n(x) := \sum_{p \in S_n} x^{r(p)} = \sum_{k = 1}^{n-1} G(n,k) x^k $$
- Observe that the coefficients of $G_n(x)$ are all even, because if $p \in S_n$ has $k$ alternating runs, then so does $p^c$, the complement of $p$, given by $p^c(i) := n + 1 - p(i)$.
- One also empirically observes that $-1$ is a root of $G_n(x)$ with multiplicity $\lfloor n/2 \rfloor - 1$, by computing $G_n(x)$ for many small values of $n$.
Bóna gives a combinatorial proof that the second observation holds for all $n > 1$, and this is essentially the content of the lemma on page 29. Some more definitions before stating it:
Let $1 \leq j \leq \lfloor n/2 \rfloor$ and $p \in 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 S_n$, define $r_j(p)$ to be the number of alternating 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$ (the number of descents of a sequence $u_1, u_2, \ldots, u_k$ is the cardinality of the set $\{i \in [k-1] : u_i > u_{i+1}\}$). Define $t_j(p) := r_j(p) + s_j(p)$, and define $$ G_{n,j}(x) := \sum_{p} x^{t_j(p)}, $$ where the sum is taken over all the $(j+1)$-half-ascending permutations $p$ in $S_n$. Now, we have the following lemma on page 29:
LEMMA 1.41
For all $n > 1$ and $0 \leq j \leq \lfloor n/2 \rfloor -1$, we have $$ \frac{G_n(x)}{2(1+x)^j} = G_{n,j}(x). $$
The proof is purportedly by induction. The base cases are easy: this is how they go.
Base case I: $j=0$ and $n \geq 2$.
A $1$-half-ascending permutation $p \in S_n$ satisfies the single constraint $p_{n-1} < p_n$. Clearly, $r_0(p) = r(p)$ and $s_0(p) = 0$, so $t_0(p) = r(p)$. Since $r(p) = r(p^c)$, and for every $p \in S_n$ either $p$ or $p^c$ is $1$-half-ascending, we see that $$ \frac{G_n(x)}{2} = G_{n,0}(x), $$ as required.
Base Case II: $j = 1$ and $n \geq 4$.
A similar argument as in the previous case shows that $$ \frac{G_n(x)}{2} = \sum_{p : p_{n-3} < p_{n-2}} x^{r(p)}. $$ Let $I \colon S_n \to S_n$ be the involution defined by $I(p_1\dotsm p_{n-2}p_{n-1}p_n) := p_1\dotsm p_{n-2}p_n p_{n-1}$, that is, $I$ 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$. 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')$, so that $$ \sum_{q(p)} x^{r(q)} = \sum_{q'(p)} x^{t_1(q')} = G_{n,1}(x). $$ Hence, $$ \frac{G_n(x)}{2(1+x)} = G_{n,1}(x), $$ as required.
Now, how does one check that $r(q) = t_1(q')$? Note that it suffices to check this in the case $n = 4$, because it is only the last $4$ terms in the sequence $p_1,\dotsc,p_n$ that are really relevant here. Thus, one just writes down all $6$ pairs of elements of the form $(p,I(p))$ where $p \in S_4$ is $2$-half-ascending, and checks that $t_1(p)$ equals the number of alternating runs of that permutation between $p$ and $I(p)$ which has smaller number of alternating runs.
This completes the second base case.
Induction Step.
Now, this is what Bóna has to say regarding the induction step (on pages 29–30):
Now let us assume that we know that the statement holds for $j-1$ and prove it for $j$. 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. $\blacksquare$
Quite frankly, this is completely confusing and I can find no interpretation of this paragraph that actually works. For example, what does
. . .apply the induction hypothesis to the leftmost $n-2$ elements. . .
mean? How does one apply the induction hypothesis to individual elements? This is just one of many points due to which the given outline for the inductive step does not go through, in my opinion. Can anyone help me find out how to fix the proof, or even exhibit how the inductive step works in the case $n = 6$?
References
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.
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.
This question has been answered on MathOverflow; the author, Miklós Bóna, posted a new proof.