+0

# Please Melody or Alan help!!! I am stuck, and please explain thoroughly!!!

+5
735
15
+561

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.

Aug 3, 2020
edited by iamhappy  Aug 5, 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.

Aug 3, 2020
#2
+561
+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
#3
+561
+4

Don't get me wrong though, it is a great answer, I just got a bit confused, and couldn't follow on. :( Thanks anyways for your time and effort, and skill!!!

iamhappy  Aug 4, 2020
edited by iamhappy  Aug 4, 2020
edited by iamhappy  Aug 5, 2020
#4
+117845
+1

Happy, I may take a look for you but I keep telling people, one post = 1 question.

Normally I will not look at posts with more than one question.

Melody  Aug 5, 2020
#5
+561
+3

well, sorry, I must've forgot. I just got carried away with the fact that it was a part a and part b question

iamhappy  Aug 5, 2020
#6
+117845
+2

I have not worked through it yet but I like the smiley face context.  :)

Aug 5, 2020
#7
+561
+3

me too! just a little hard to follow for my small brain. :) :P

iamhappy  Aug 5, 2020
#8
+561
+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

Aug 5, 2020
#9
+117845
+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.}

Aug 5, 2020
#10
+117845
+1

I would prove this with induction.  Have you done induction yet?

Aug 5, 2020
#11
+117845
+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}\\

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}

Aug 5, 2020
#12
+561
+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
edited by iamhappy  Aug 5, 2020
#13
+117845
+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
#14
+561
+3

honestly, I didn't either, I just kind of slightly ignored it. I also did the problem, but my explanation defiitely was not clear at all. I need to work on that. :)

iamhappy  Aug 5, 2020
#15
+561
+3

And I should mention, I got the same answer, just I didn't know how to correctly do it.

iamhappy  Aug 5, 2020