Exercise 1.22

Question

The Dutch mathematician R.J. Stroeker remarked:
Every beginning student of number theory surely must have marveled at the miraculous fact that for each natural number $n$ the sum of the first $n$ positive consecutive cubes is a perfect square. [26]
Furthermore, it is the square of the sum of the first $n$ positive integers! That is,
$$
1^{3}+2^{3}+\cdots+n^{3}=(1+2+\cdots+n)^{2} .
$$
Usually this identity is proven by induction, but that does not give much insight into why the result is true, nor does it help much if we wanted to compute the left-hand side but didn't already know this result. In this problem, you will give a story proof of the identity.
ewline
(a) Give a story proof of the identity
$$
1+2+\cdots+n=\left(\begin{array}{c}
n+1 \
2
\end{array}ight) 	ext {. }
$$
Hint: Consider a round-robin tournament (see \href{./exercise_1-4}{Exercise 4}).
ewline
(b) Give a story proof of the identity
$$
1^{3}+2^{3}+\cdots+n^{3}=6\left(\begin{array}{c}
n+1 \
4
\end{array}ight)+6\left(\begin{array}{c}
n+1 \
3
\end{array}ight)+\left(\begin{array}{c}
n+1 \
2
\end{array}ight)
$$
It is then just basic algebra (not required for this problem) to check that the square of the right-hand side in (a) is the right-hand side in (b).
Hint: Imagine choosing a number between 1 and $n$ and then choosing 3 numbers between 0 and $n$ smaller than the original number, with replacement. Then consider cases based on how many distinct numbers were chosen.

fifthist x · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item   Let us count the number of games in a round-robin tournament with $n+1$ 
participants in two ways.
  
  Method 1: Since every player plays against all other players exactly once, 
  the problem reduces to finding the number of ways to pair up $n+1$ people. 
  There are ${n+1 \choose 2}$ ways to do so.
  
  Method 2: The first player participates in $n$ games. The second one also 
  participates in $n$ games, but we have already counted the game against the 
  first player, so we only care about $n-1$ games. The third player also 
  participates in $n$ games, but we have already counted the games against 
  the first and second players, so we only care about $n-2$ games. 
  
  In general, player $i$ will participate in $n+1-i$ games that we care about. 
  Taking the sum over $i$ we get
  
  $$n + (n-1) + (n-2) + \dots + 2 + 1$$
  
  Since both methods count the same thing, they are equal.

\item LHS: If $n$ is chosen first, then the subsequent $3$ numbers can be any 
of $0, 1, \dots, n-1$. These $3$ numbers are chosen with replacement resulting 
in $n^{3}$ possibilities. Summing over possible values of 
$n$ we get $1^{3} + 2^{3} + \dots + n^{3}$ total number of possibilities.
  
  RHS: We can count the number of permutations of the $3$ numbers chosen with 
  replacement from a different perspective. The $3$ numbers can either all be 
  distinct, or all be the same, or differ in exactly $1$ value.
  
  Case 1: All $3$ numbers are distinct.
  
  Selecting $4$ (don't forget the very first, largest selected number) 
  distinct numbers can be done in ${n+1 \choose 4}$ ways. The $3$ smaller 
  numbers are free to permute amongst themselves. This gives us a total of 
  $6{n+1 \choose 4}$ possibilities.
  
  Case 2: All $3$ numbers are the same.
  
  In this case, we have to select $2$ digits. The smaller digit will be sampled 
  $3$ times and there are no ways to permute identical numbers, so the number of 
  possiblities is ${n+1 \choose 2}$.
  
  Case 3: Two of the $3$ numbers are distinct.
  
  In this case, we have to select $3$ digits in total. One of the smaller $2$ 
  digits will be sampled twice, giving us $3$ permutations. Since, there are $2$ 
  choices for which digit gets sampled twice, we get a total of $6$ permutations. 
  The total number of possibilities then is $6{n+1 \choose 3}$.
  
  Adding up the number of possibilities in each of the cases we get a total of 
  $$6{n+1 \choose 4} + 6{n+1 \choose 3} + {n+1 \choose 2}$$ possibilities. 
  
  Since the LHS and the RHS count the same set, they are equal.

\end{enumerate}

Exercise 1.22

Answers

Comments

Exercise 1.22

Answers

Comments

Add answer