SOLUTION: Let S = {1,2,..., n+1} where n>=2, and let T= { (x,y,z)∈ S^3 |x < z and y < z}.Show by counting |T| in two different ways that: nΣk=1 k^2 = |T| = (n+1 choose 2) + 2(n+1 choose 3

Question 1164826: Let S = {1,2,..., n+1} where n>=2, and let T= { (x,y,z)∈ S^3 |x < z and y < z}.Show by counting |T| in two different ways that: nΣk=1 k^2 = |T| = (n+1 choose 2) + 2(n+1 choose 3)
Answer by CPhill(2189) (Show Source): You can put this solution on YOUR website!
To show this identity, we will count the number of elements in the set where .
---
### Method 1: Summing based on the value of
In this method, we fix the value of and count how many pairs satisfy the condition and .
1. The possible values for are because must be strictly greater than and , and the smallest value in is 1.
2. If we fix (where ranges from to ):
* The values of must be chosen from the set . There are choices for .
* The values of must also be chosen from the set . There are choices for .

3. For a fixed , there are possible pairs .
4. Summing over all possible values of from to :

---
### Method 2: Counting by Cases of and
Now, we count the same set by considering the relationship between and . There are two main scenarios: either or .
**Case 1: **
If , then the condition and simplifies to . We just need to choose two distinct numbers from and assign the larger one to and the smaller one to (and ).
* Number of ways to choose 2 distinct elements from : .
**Case 2: **
If , we are choosing three values such that is the largest. First, we choose 3 distinct numbers from the available numbers. Let these be where .
* To satisfy the condition, **must** be the largest value ().
* For the remaining two values ( and ), one must be and the other must be .
* There are 2 possibilities: or .
* Number of ways to choose 3 elements and arrange them: .
### Conclusion
By combining the two cases in Method 2, we get:

Since both methods count the exact same set , we have proven that:

---
Would you like me to show how this expression simplifies further to the standard formula ?
RELATED QUESTIONS
Hello, I'm at a loss of how to solve this. Any help would be very much appreciated.... (answered by Edwin McCravy)

Suppose Z is a standard normal random variable and let Y = aZ +b, where a > 0 and b are... (answered by ikleyn)

[x] = [ ]+[ ] +[ ] [y] = [ ]+[ ]s+[ ]t. [z] = [ ]+[ ] +[ ] x= (1/2) - (3/2)*s -... (answered by ikleyn)

[x] = [ ]+[ ] +[ ] [y] = [ ]+[ ]s+[ ]t. [z] = [ ]+[ ] +[ ] x= (1/2) -... (answered by ikleyn)

Two lines have equations L1 :[x,y,z] = [1,3,2] + t[3,0,-1] L2 :[x,y,z] = [3,1,-2] +... (answered by Edwin McCravy)

Solve by the Gauss-Jordan elimination: x+y+2z+t=1 x+2y+z+t=2 2x+y+z+t=4... (answered by Edwin McCravy)

Let T(x,y,z) = (y,z,0). Prove that T^3 must be a zero transformation... (answered by user_dude2008)

Let X and Y be independent random variables with distributions... (answered by textot)

1. Whenever we encounter a new proposition, it is a good idea to explore the proposition (answered by richard1234)