Let \(n\) be a positive integer.
(a) Prove that \(n^3 = n + 3n(n - 1) + 6 \dbinom{n}{3}\)
by counting the number of ordered triples \((a,b,c)\) where \(1 \le a,b,c,\le n\), in two different ways.
(b) Prove that \(\dbinom{n + 2}{3} = (1)(n) + (2)(n - 1) + (3)(n - 2) + \dots + (k)(n - k + 1) + \dots + (n)(1),\)
by counting the number of subsets of \(\{1, 2, 3, \dots, n + 2\}\) containing three different numbers in two different ways.
(a) Let's call (a,b,c) a smiley face if b is less than a and b is less than c, because when we plot the graph, we get a happy face! And if b is greater than a and b is greater than c, that's a frowny face, because we get a frowny face when we turn a smiely face up-side-down.
There are other kinds of faces like smirks (like a is less than b and b is less than c) and neutral faces (like when a is equal to b and b is equal to c). If the face is neutral, then a equals b and b equals c, so when we choose a, b, and c are also chosen, and there are n choices for a, so there are n neutral faces.
Now we count the number of smirks. There are n ways to choose a, and there are n - 1 ways to choose b. We also multiply by 3, because the value that we chose for a could have also been the value of b, or the value of c. So there are 3n(n - 1) smirks.
Now we count the number of smiley faces. There are n ways to choose a, then n - 1 ways to choose b, then n - 2 ways to choose c. So there are n(n - 1)(n - 2) = 3C(n,3) smiley faces. By symmetry, there are 3C(n,3) frowny faces.
Therefore, the total number of faces is n^3 = n + 3n(n - 1) + 6C(n,3).
(b) To choose three numbers, we can choose two groups one group with two numbers and the other group has one number. The total of n + 2 numbers can be separated into two groups.
In the first way, one group has 2 numbers, and the other group has n numbers. They form a total of n + 2 numbers. There are C(2,2) = 1 ways to choose two numbers from the 2 group. There are C(n,1) = n ways to choose one number from the one group. This gives us a first term of 1*n.
In the second way, one group has three numbers, and the other group has n - 1 numbers. They form a total of n - 1 numbers. There are C(3,2) = 2 ways to choose two numbers from the 2 group. There are C(n - 1,1) = n - 1 ways to choose one number from the one group. This gives us a second term of 2*(n - 1). The pattern will continue until we reach n. So the two sides are equal.
+59 Solution:
(a) The number of ordered triples \( (a,b,c),\) where \( 1 \le a, b,c \le n,\) is \(n^3\) We can classify these triples into three categories.
Case 1: \(a,b,c\) are all equal.
There are \(n\) ordered triples in this case.
Case 2: Two of \(a,b,c\) are equal, and the third is different.
There are \(n\) ways to choose the two equal values, then \(n-1\) ways to choose the third value that is different. There are then \(3\) ways to arrange the numbers within the ordered triple, so the number of ordered triples in this case is \(3n(n-1).\)
Case 3: \(a,b,c\) are all different.
There are \(\dbinom{n}{3}\) ways to choose three different values. There are then \(3!=6\) ways to arrange them, so the number of ordered triples in this case is \(6\dbinom{n}{3}\)
By counting the number of triples \((a,b,c)\) in two different ways, we arrive at the conclusion
\(n^3=n+3n(n-1)+6\dbinom{n}{3}. \)
(b) The number of subsets of \(\{1,2,3,...,n+2\}\) containing three different numbers is \(\dbinom{n+2}{3}\)
We can also count the number of subsets as follows. Let the subset be \(\{a,b,c\},\) where \(a Then the middle element \(b\) is at least \(2\) and at most \(n+1\) so we can let \(b=k+1\) where \(1\le k \le n.\)
Once the middle element \(b=k+1\) is chosen, the smallest element \(a\) must be between \(1\) and \(k\) inclusive, so there are \(k\) ways of choosing the smallest element \(a\). The largest element \(c\) must be between \(k+2\) and \(n+2\) inclusive, so there are \((n+2)-(k-2)+1\) ways of choosing the largest element \(c\). So the number of subsets where the middle element is \(k+1\) is \(k(n-k+1)\) Summing over \(1 \le k \le n\) we get
\(\dbinom{n+2}{3}=(1)(n)+(2)(n-1)+(3)(n-2)+\cdots+(k)(n-k+1)+\cdots+(n)(1).\)
