0
$\begingroup$

In other words, you have an ordered finite list of numbers which is sorted ascendingly (without loss of generality), for example [1,2,5,7,10,12]. Remove elements from the list, the list is still sorted. Prove this mathematically.

I know this is intuitive but how to prove it mathematically.

I tried induction but I struggled with mathematical representation of a sorted list (how to denote a sorted list mathematically).

Any help please?

$\endgroup$
2
  • 1
    $\begingroup$ My first stab would be using induction on the number of elements removed from the list. Your base case ($n=0$) is obviously true, and the inductive step would involve removing a single element from a sorted list. $\endgroup$
    – MPW
    Commented Sep 18, 2015 at 2:10
  • $\begingroup$ Thanks. This is an elegant proof which does not require any mathematical representation. $\endgroup$
    – user215750
    Commented Sep 18, 2015 at 2:13

1 Answer 1

2
$\begingroup$

Suppose

$$a_1, a_2, \ldots, a_n$$

is sorted. This means

$$i \geq j \implies a_i \geq a_j \tag{1}$$

Now we remove $a_k$.

$$a_1, \ldots, a_{k-1}, a_{k+1}, \ldots, a_n$$

Now show that this new list satisfies the property of a sorted array. If $i \geq j$ and $i,j \neq k$, then it is still true that $a_i \geq a_j$ from $(1)$. Thus the array is still sorted.

$\endgroup$

You must log in to answer this question.