proof of misplacement in array

Question

suppose we have an array $A$ and we have a misplacement such if $i < j$ then $A[i] > A[j] $
prove that if we have a misplacement in our array then we have at least $ j - i$ misplacement in our array

Answer 1

We have a misplacement with: If $i < j$ then $A[i] > A[j] $

$i < j$ means that there is a $k$ such as $i<k<j$ and $j-i=k$

Let's prove that we have at least $k$ misplacements in our array $A$.

For all $k$ a defined above $A[k] = A[j-i]$

Let's now use a reductio ad absurdum argument. Suppose that there is only one misplacement and for all $k$ we have $A[i] < A[k] < A[j]$

This contradictory to $A[i] > A[j]$

This means that $A[j] < A[k] < A[i]$ for all $k = j-i$

Thus we have at least k misplacements such as $A[j] < A[k]$