We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
-1
94
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+121 
+4

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+54 
0

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+54 
0

Like i dont think anybody cares

Leaded  Oct 28, 2019
 #4
avatar
+1

(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

12 Online Users