would use mathematical induction apparently but don't get the way on proving could anybody give proof?

Skravin wrote: would use mathematical induction apparently but don't get the way on proving could anybody give proof? It doesn't use induction

Any solution?

the following partitions may help $C^+== \{ 1 \le i \le n : a_i >a_{i-1}, a_{i+1} \}$ $C^-== \{ 1 \le i \le n : a_i <a_{i-1}, a_{i+1} \} $ $F^+== \{ 1 \le i \le n : a_i >a_{i-k}, a_{i+k} \}$ $F^-== \{ 1 \le i \le n : a_i <a_{i-k}, a_{i+k} \} $ $C^+,C^-$ is a partition of the set of $a_i$ $F^+,F^-$ is a partition of the set of $a_i$ and $A,B,C$ can easy be write using those sets

aviateurpilot wrote: $C^+,C^-$ is a partition of the set of $a_i$ $F^+,F^-$ is a partition of the set of $a_i$ and $A,B,C$ can easy be write using those sets No it isn't

Bump this

If you make a graph connecting $i$ and $i \pm 1, i \pm k$, and then attach $2$-cells along $i \to i+1 \to i+k+1 \to i+k \to i$, then you get a torus and $a_i$ may be interpreted as a function on this torus. Then you can use something like Morse theory. ($A$ is like local maxima or local minima, $B$ and $C$ are counting saddle points, but there actually more saddle points coming from the interior of the $2$-cells. Then $\chi(T^2) = 0$ gives the inequality.) Of course, this is completely unnecessary; I think there was a proof using double-counting of some sort, if you do local analysis of the orders between $a_i, a_{i+1}, a_{i+k+1}, a_{i+k}$. I remember the difference $\lvert A \rvert - \lvert B \rvert - \lvert C \rvert$ was some constant times the number of some configuration.

Quote: Of course, this is completely unnecessary; I think there was a proof using double-counting of some sort, if you do local analysis of the orders between $a_i, a_{i+1}, a_{i+k+1}, a_{i+k}$. I remember the difference $\lvert A \rvert - \lvert B \rvert - \lvert C \rvert$ was some constant times the number of some configuration. My solution : count the triples of kind $(a_{i+1}<a_i>a_{i+k}) , (a_{i+1}>a_i>a_{i+k}),...$ etc. and those of kind $(a_{i-1}<a_i>a_{i+k}) , (a_{i-1}>a_i>a_{i+k}),...$ etc. It turns out after some analysis that $\lvert A \rvert \ge \lvert B \rvert + \lvert C \rvert$ reduces to showing that the number $X$ of such triples for which $a_i$ is not between $a_{i+1},a_{i+k}$ (or $a_{i-1} , a_{i+k}$) is greater than the number $Y$ of triples for which $a_i$ is between the two terms. Then the fact that $a_i, a_{i+1}, a_{i+k+1}, a_{i+k}$ cannot form a cycle eventually proves that $X \ge Y$.