Average length of the longest $k$-alternating subsequence

We prove a conjecture of Drew Armstrong on the average maximal length of $k$-alternating subsequence of permutations. The $k=1$ case is a well-known result of Richard Stanley.