Let n be a positive integer.

(a) Prove that \(n^3 = n + 3n(n - 1) + 6 \binom{n}{3}\)

by counting the number of ordered triples (a, b) of positive integers, where \(1 \le a,\) b, \(c \le n,\) in two different ways.

(b) Prove that. \(\binom{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.

iamhappy Aug 3, 2020

#1**+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.

Guest Aug 3, 2020

#2**+5 **

hi guest, great job, but I am slightly confused why you used smiley faces instead of things that may be more understandable. It may just be that there is something wrong with my brain, but I am a little confused on why you took that approach. :)

iamhappy
Aug 4, 2020

#8**+3 **

I have started by finding these three cases

1. a, b and c are equal. Let's name this case, case 1

2. two out of the three integers are equal. (example could be a and b are equal, but c is different, etc.) Let's name this case, case 2

3. a, b, and c are different. Let's name this case, case 3

iamhappy Aug 5, 2020

#9**+2 **

a)

\(\text{Prove that } n^3 = n + 3n(n - 1) + 6 \binom{n}{3}\\ \text{by counting the number of ordered triples (a, b) of positive integers}, \\\text {where } 1 \le a,b,c \le \text{in two different ways.}\)

So far I do not understand what this question is on about.

You are asked to prove something, where the only letter used, is n

then a, b and c are introduced to use in the solution. Where did a, b and c come from?

\text{Prove that } n^3 = n + 3n(n - 1) + 6 \binom{n}{3}\\

\text{by counting the number of ordered triples (a, b) of positive integers}, \\\text {where } 1 \le a,b,c \le \text{in two different ways.}

Melody Aug 5, 2020

#11**+4 **

a)

\(\text{Prove that } n^3 = n + 3n(n - 1) + 6 \binom{n}{3}\\ \text{by counting the number of ordered triples (a, b) of positive integers}, \\\text {where } 1 \le a,b,c \le \text{in two different ways.}\\ Where \;\;\;n\ge3\;\;\;and \;\;\;n\in Z\)

I am going to prove this using Induction.

__STEP 1__

Prove true for n=3

\(LHS=n^3 \\ LHS=3^3 \\ LHS=27\\ RHS= n + 3n(n - 1) + 6 \binom{n}{3}\\ RHS= 3 + 3*3(3 - 1) + 6 \binom{3}{3}\\ RHS= 3 + 18 + 6 \\ RHS=27\\ RHS=LHS\\ \text{So the statement is true for n=3}\)

__STEP 2__

If true for n=k prove true for n=k+1

so we can assume

\(k^3=k+3k(k-1)+6\binom{k}{3}\\ k^3=k+3k^2-3k+6\binom{k}{3}\\ k^3=3k^2-2k+6\binom{k}{3}\\\)

Now I need to prove it will be true for n=k+1

i.e. Prove

\((k+1)^3=(k+1)+3(k+1)(k+1-1)+6\binom{k+1}{3}\\ (k+1)^3=(k+1)+3(k+1)(k)+6\binom{k+1}{3}\\ \qquad \qquad \qquad \text{An aside:}\\ \qquad \qquad \qquad \binom{k+1}{3}=\frac{(k+1)!}{3!(k+1-3)!}\\ \qquad \qquad \qquad \binom{k+1}{3}=\frac{k!(k+1)}{3!(k-3)!(k-2)}\\ \qquad \qquad \qquad \binom{k+1}{3}=\frac{(k+1)}{(k-2)}*\binom{k}{3}\\ \qquad \qquad \qquad \binom{k+1}{3}=\frac{(k+1)}{(k-2)}*\binom{k}{3}\\ \qquad \qquad \qquad \binom{k+1}{3}=\frac{(k-2)+3}{(k-2)}*\binom{k}{3}\\ \qquad \qquad \qquad \binom{k+1}{3}=\binom{k}{3}+\frac{3}{k-2}*\binom{k}{3}\\\)

\(LHS=(k+1)^3\\ LHS=k^3+3k^2+3k+1\)

\(RHS=(k+1)+3(k+1)(k)+6\binom{k+1}{3}\\ RHS=(k+1)+3(k+1)(k)+6\left[ \binom{k}{3}+\frac{3}{k-2}*\binom{k}{3}\right]\\ RHS=k+1+3k^2+3k+6 \binom{k}{3}+\frac{6*3}{k-2}*\binom{k}{3}\\ RHS=1+3k^2+4k+6 \binom{k}{3}+\frac{6*3}{k-2}*\binom{k}{3}\\ RHS=3k^2-2k+1+6 \binom{k}{3}+6k+\frac{6*3}{k-2}*\binom{k}{3}\\ substituting\\ RHS=k^3+6k+1+\frac{6*3}{k-2}*\binom{k}{3}\\ RHS=k^3+6k+1+\frac{6*3}{k-2}*\frac{k!}{3!(k-3)!}\\ RHS=k^3+6k+1+\frac{6*3}{k-2}*\frac{(k-3)!(k-2)(k-1)k}{3!(k-3)!}\\ RHS=k^3+6k+1+\frac{6*3}{1}*\frac{(k-1)k}{3!}\\ RHS=k^3+6k+1+3k^2-3k\\ RHS=k^3+3k^2+3k+1\\ RHS=LHS\\~\\ \text{So if it is true for n=k then it will be true also for n=k+1} \)

__Step 3__

**Since it is true for n=3 it must be true for n=4, n=5, n=6, ....**

**Hence it must be true for all integer n where n greater or equal to 3.**

LaTex:

\text{Prove that } n^3 = n + 3n(n - 1) + 6 \binom{n}{3}\\

\text{by counting the number of ordered triples (a, b) of positive integers},

\\\text {where } 1 \le a,b,c \le \text{in two different ways.}\\

Where \;\;\;n\ge3\;\;\;and \;\;\;n\in Z

LHS=n^3 \\

LHS=3^3 \\

LHS=27\\

RHS= n + 3n(n - 1) + 6 \binom{n}{3}\\

RHS= 3 + 3*3(3 - 1) + 6 \binom{3}{3}\\

RHS= 3 + 18 + 6 \\

RHS=27\\

RHS=LHS\\

\text{So the statement is true for n=3}

k^3=k+3k(k-1)+6\binom{k}{3}\\

k^3=k+3k^2-3k+6\binom{k}{3}\\

k^3=3k^2-2k+6\binom{k}{3}\\

(k+1)^3=(k+1)+3(k+1)(k+1-1)+6\binom{k+1}{3}\\

(k+1)^3=(k+1)+3(k+1)(k)+6\binom{k+1}{3}\\

\qquad \qquad \qquad \text{An aside:}\\

\qquad \qquad \qquad \binom{k+1}{3}=\frac{(k+1)!}{3!(k+1-3)!}\\

\qquad \qquad \qquad \binom{k+1}{3}=\frac{k!(k+1)}{3!(k-3)!(k-2)}\\

\qquad \qquad \qquad \binom{k+1}{3}=\frac{(k+1)}{(k-2)}*\binom{k}{3}\\

\qquad \qquad \qquad \binom{k+1}{3}=\frac{(k+1)}{(k-2)}*\binom{k}{3}\\

\qquad \qquad \qquad \binom{k+1}{3}=\frac{(k-2)+3}{(k-2)}*\binom{k}{3}\\

\qquad \qquad \qquad \binom{k+1}{3}=\binom{k}{3}+\frac{3}{k-2}*\binom{k}{3}\\

LHS=(k+1)^3\\

LHS=k^3+3k^2+3k+1

RHS=(k+1)+3(k+1)(k)+6\binom{k+1}{3}\\

RHS=(k+1)+3(k+1)(k)+6\left[ \binom{k}{3}+\frac{3}{k-2}*\binom{k}{3}\right]\\

RHS=k+1+3k^2+3k+6 \binom{k}{3}+\frac{6*3}{k-2}*\binom{k}{3}\\

RHS=1+3k^2+4k+6 \binom{k}{3}+\frac{6*3}{k-2}*\binom{k}{3}\\

RHS=3k^2-2k+1+6 \binom{k}{3}+6k+\frac{6*3}{k-2}*\binom{k}{3}\\

substituting\\

RHS=k^3+6k+1+\frac{6*3}{k-2}*\binom{k}{3}\\

RHS=k^3+6k+1+\frac{6*3}{k-2}*\frac{k!}{3!(k-3)!}\\

RHS=k^3+6k+1+\frac{6*3}{k-2}*\frac{(k-3)!(k-2)(k-1)k}{3!(k-3)!}\\

RHS=k^3+6k+1+\frac{6*3}{1}*\frac{(k-1)k}{3!}\\

RHS=k^3+6k+1+3k^2-3k\\

RHS=k^3+3k^2+3k+1\\

RHS=LHS\\~\\

\text{So if it is true for n=k then it will be true also for n=k+1}

Melody Aug 5, 2020

#12**+5 **

Oh my goodness thank you sooo much!!!! This was really well done!!!!! I also really understood it!!! THANK YOU!!!

p. s. in my time zone, when you published the answer, it was already like 3 am in the morning. Sorry i couldn't see it earlier. I was sleeping!!! \(:)\)

iamhappy
Aug 5, 2020

#13**+1 **

You are welcome,

I am glad you could understand it :)

I wish I understood what the a b c stuff in the question was about....

Melody
Aug 5, 2020