document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1164826>Question 1164826</A>: <I><SPAN STYLE=\"word-break: break-all;\"> 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) </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #853511 by </B><A HREF=/tutors/aboutme.mpl?userid=CPhill><B>CPhill(2189)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=CPhill><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=CPhill><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=853511\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> To show this identity, we will count the number of elements in the set  where .\r<BR>\n" );
document.write( "\n" );
document.write( "---\r<BR>\n" );
document.write( "\n" );
document.write( "### Method 1: Summing based on the value of \r<BR>\n" );
document.write( "\n" );
document.write( "In this method, we fix the value of  and count how many pairs  satisfy the condition  and .\r<BR>\n" );
document.write( "\n" );
document.write( "1. The possible values for  are  because  must be strictly greater than  and , and the smallest value in  is 1.<BR>\n" );
document.write( "2. If we fix  (where  ranges from  to ):<BR>\n" );
document.write( "* The values of  must be chosen from the set . There are  choices for .<BR>\n" );
document.write( "* The values of  must also be chosen from the set . There are  choices for .\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "3. For a fixed , there are  possible pairs .<BR>\n" );
document.write( "4. Summing over all possible values of  from  to :\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "---\r<BR>\n" );
document.write( "\n" );
document.write( "### Method 2: Counting by Cases of  and \r<BR>\n" );
document.write( "\n" );
document.write( "Now, we count the same set  by considering the relationship between  and . There are two main scenarios: either  or .\r<BR>\n" );
document.write( "\n" );
document.write( "**Case 1: **<BR>\n" );
document.write( "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 ).\r<BR>\n" );
document.write( "\n" );
document.write( "* Number of ways to choose 2 distinct elements from : .\r<BR>\n" );
document.write( "\n" );
document.write( "**Case 2: **<BR>\n" );
document.write( "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 .\r<BR>\n" );
document.write( "\n" );
document.write( "* To satisfy the condition,  **must** be the largest value ().<BR>\n" );
document.write( "* For the remaining two values ( and ), one must be  and the other must be .<BR>\n" );
document.write( "* There are 2 possibilities:  or .<BR>\n" );
document.write( "* Number of ways to choose 3 elements and arrange them: .\r<BR>\n" );
document.write( "\n" );
document.write( "### Conclusion\r<BR>\n" );
document.write( "\n" );
document.write( "By combining the two cases in Method 2, we get:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Since both methods count the exact same set , we have proven that:\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "---\r<BR>\n" );
document.write( "\n" );
document.write( "Would you like me to show how this expression simplifies further to the standard formula ? </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );