+0  
 
+1
1245
4
avatar

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.

 Oct 25, 2019
edited by Guest  Oct 25, 2019
 #1
avatar+127 
-3

Please do not post solutions to this problem!

 

This is a homework problem, and the original poster is simply trying to cheat.

 Oct 26, 2019
 #2
avatar+128 
+4

What if he actually needs help to this problem.  Dont go commenting on peoples questions the same thing "Dont post hw problems" 

Leaded  Oct 28, 2019
 #3
avatar+128 
+4

Like i dont think anybody cares

Leaded  Oct 28, 2019
 #4
avatar
+3

(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.

 Nov 3, 2019

42 Online Users

avatar
avatar
avatar