Let's say I have a sequence of (distinct) monotonically increasing numbers S. I'll want to add them sequentially to a Binary Search Tree (BST) but as the numbers are monotonically increasing the resulting tree will be unbalanced (the tree will be nothing but a linked-list).
To correct this problem, I can devise another sequence S' containing all the elements of S but in a different order. For instance, if $S = { 1..9 }$, then $S' = { 5, 2, 7, 1, 3, 6, 8, 4, 9 }$ would yield a balanced tree were I to add all these integers to an initially empty BST. The formula I followed was informally
$a_{ij} = i + \frac{j-i+1}{2}$
It's easy for me to do this on paper or even to implement a function in a programming language that making use of a queue can yield S' from S (for an arbitrary value of n) but I'm quite lost on how to do this making use of either sequences or recurrences.
How would I go about "formalizing" this mathematically, without resorting to pseudo-code?