For positive integer n, Prove that 1 2 + 2 3 + + n(n + 1) = 1/3 n(n + 1)(n + 2), by considering the following counting problem. (1) Let A denote the number of 3-lists (a, b, c) with no repeat, where a, b, c {1, 2, , n + 2}, such that a is the maximum among the three (that is, b < a and c < a). Show that for fixed a, there are 0 choices for b and c if a = 1 or a = 2, and that there are (a 1)(a 2) choices for b and c if a is at least 3. Conclude that A = 1 2 + 2 3 + + n(n + 1). (2) Let B denote the number of triples (a, b, c), where 1 a, b, c n + 2, such that no two of them are equal, and b is the maximum among the three. Also, let C denote the number of triples (a, b, c), where 1 a, b, c n + 2, such that no two of them are equal, and c is the maximum among the three. Using symmetry among a, b and c, or by classification according to b in the case of B and to c in the case of C and repeating the argument in (1)(2) above, conclude that A = B = C. (3) Show that A+B +C equals the number of 3-lists (a, b, c) with no repeat, where a, b, c {1, 2, , n +2} (without any other restrictions), by mimicking our arguments in the example discussed in class. Conclude that A + B + C = n(n + 1)(n + 2). (4) Conclude that 1 2 + 2 3 + + n(n + 1) = 1 3 n(n + 1)(n + 2)