组合数学问题求助：证明平方和与集合T基数的等式

给定集合 ( S \equiv {1,2,\ldots,n +1} )（其中 ( n \geq 2 )），以及集合：
$$
T \equiv \left{(x,y,z) \in S^{3} \mid x < z, y < z \right}
$$
需要证明等式：
$$
\sum_{k = 1}^{n}k{2} = \vert T\vert = \binom{n + 1}{2} + 2\binom{n + 1}{3}
$$

我的进展与困惑 #

• 我已经能用简单的组合论证证明右边的等式（( \vert T\vert = \binom{n + 1}{2} + 2\binom{n + 1}{3} )）成立了。
• 但我不知道怎么证明左边的等式（( \sum_{k = 1}^{n}k{2} = \vert T\vert )），希望能得到帮助或者提示。

证明左边等式的思路提示 #

别发愁，我们可以换个分类计数的角度来数集合 ( T ) 的元素个数，直接和平方和建立对应关系：

核心思路是固定z的取值来拆分计数：
因为T中的元素要求 ( x < z ) 且 ( y < z )，我们可以按z的不同取值来统计每个z对应的(x,y)对数量：

• 当 ( z=2 ) 时，x和y只能取1，有 ( 1 \times 1 = 1^2 ) 个元素；
• 当 ( z=3 ) 时，x和y可以取1或2，各有2种选择，对应 ( 2 \times 2 = 2^2 ) 个元素；
• ...
• 当 ( z=k+1 )（k从1到n）时，x和y可以取1到k中的任意数，各有k种选择，对应 ( k \times k = k^2 ) 个元素；
• 当 ( z=n+1 ) 时，x和y可以取1到n，对应 ( n \times n = n^2 ) 个元素。

把所有z对应的元素个数加起来，集合T的总元素数就是：
$$
1^2 + 2^2 + \dots + n^2 = \sum_{k=1}^n k^2
$$
这样就直接证明了 ( \sum_{k = 1}^{n}k{2} = \vert T\vert ) 啦！

备注：内容来源于stack exchange，提问作者Michele