MathDB

Let

m, n

be positive integers. Consider a sequence of positive integers

a_1, a_2, ... , a_n

that satisfies m = a_1 \ge a_2\ge ... \ge a_n \ge 1. Then define, for 1\le i\le m,

b_i =

# \{ j \in \{1, 2, ... , n\}: a_j \ge i\}, so

b_i

is the number of terms

a_j

of the given sequence for which a_j \ge i. Similarly, we define, for 1\le j \le n,

c_j=

# \{ i \in \{1, 2, ... , m\}: b_i \ge j\} , thus

c_j

is the number of terms bi in the given sequence for which b_i \ge j. E.g.: If

a

is the sequence

5, 3, 3, 2, 1, 1

then

b

is the sequence

6, 4, 3, 1, 1

. (a) Prove that

a_j = c_j

for 1 \le j \le n. (b) Prove that for 1\le k \le m:

\sum_{i=1}^{k} b_i = k \cdot b_k + \sum_{j=b_{k+1}}^{n} a_j

3