Proof of equality involving factorials

[mindauggas]

Hello everyone

Homework Statement

i don't see a connection why C_iⁿ = $\frac{(n*(n-1)*(n-2)*...*(n-i+1))}{1*2*...*i }$ = $\frac{n!}{i!(n-i)!}$

Is there a way to simplify them in order to see why the equality holds?

The Attempt at a Solution

the definition of factorial being n!=1*2*...*n I expressed it as
n! = (n-(n-1))(n-(n-2))...(n-(n-n)).
Is this wrong? the idea was that (n-(n-1)) = 1 (I expressed all the factorials in the same way; tried to simplify something).

I also tried to express n!/i!(n-i)! as such: 1*2*...*n/1*2*...i*(n-i)!

This is a problem form Courant/Robbin/Stewart - "What is Mathematics" pp 17.
Thank you very much for your time and help.

 

[tiny-tim]

welcome to pf!

hello mindauggas! welcome to pf!

what do you have to multiply the top by to get n! ? ​

 

[mindauggas]

Cant see the solution even with the hint... probably that component that i have to multiply has to have "i" in it, but no idea what it is

I don't think i will be able to intuit the component by which i have to multiply if there is no way to simplify the function ... my mathematical intuition is not very developed

can anyone write the beginning of the solution?

 

[Skins]

Think of this You can write (expand) $$n!$$ on the top as

$$n(n-1)(n-2)...(n-i+1)(n-i)!$$

How might that help you ? Think about what you have on top. Is there anything the same on the bottom ?

 

[vela]

You might find it easier to go the other way. Expand the factorials in
$$\frac{n!}{i!(n-i)!}$$
and simplify. If using variables confuses you, it may help to try specific numbers for n and i to identify the pattern.

 

[mindauggas]

Thank guys you for your help. I understood everything except one thing, this is what i did.

C_iⁿ= $\frac{(n∗(n−1)∗(n−2)∗...∗(n−i+1))(n-1)!}{i!}$ = $\frac{n!}{i!(n−i)!}$

obtained n∗(n−1)∗(n−2)∗...∗(n−i+1)(n-1) = n!
expanded the n! and divided both sides by n, thus getting:
(n−1)∗(n−2)∗...∗(n−i+1)(n-1)!= 1*2*...*(n-1), because the right side is just (n-1)! the only way that statement is true is if
(n−1)∗(n−2)∗...∗(n−i+1) = 1

This is what is not clear, whys is the left side equal to one? Or is not equal to one?

 

[tiny-tim]

hi mindauggas!

obtained n∗(n−1)∗(n−2)∗...∗(n−i+1)(n-1) = n!
expanded the n! and divided both sides by n, thus getting:
(n−1)∗(n−2)∗...∗(n−i+1)(n-1)!= 1*2*...*(n-1)

(i assume your first line was meant to be n∗(n−1)∗(n−2)∗...∗(n−i+1)(n-1)! = n! ?)

i'm sorry, but this is nonsense … where did you get it from?

try it with n = 12 and i = 5, so you can see how it works

so n∗(n−1)∗(n−2)∗...∗(n−i+1) = 12*11*10*9*8 …

now that is 12! over what? ​

 

[mindauggas]

hi mindauggas!


(i assume your first line was meant to be n∗(n−1)∗(n−2)∗...∗(n−i+1)(n-1)! = n! ?)

i'm sorry, but this is nonsense … where did you get it from?

try it with n = 12 and i = 5, so you can see how it works

so n∗(n−1)∗(n−2)∗...∗(n−i+1) = 12*11*10*9*8 …

now that is 12! over what? ​

This is how I got it:

n∗(n−1)∗(n−2)∗...∗(n−i+1)(n-1)! = n!

expand n!:

n∗(n−1)∗(n−2)∗...∗(n−i+1)(n-1)! = 1*2*...*n

dividing both sides by n we obtain

(n-1)*(n-2)*...*(n-i+1)*(n-1)! = 1*2*...*(n-1)

the last member is (n-1) if i reason correctly, so this means that that the whole right side is just (n-1)!

then i divide both sides by (n-1)! to obtain:

(n−1)∗(n−2)∗...∗(n−i+1) = 1

How can this be the case? My logic is definitely flawed somewhere. Can anyone point oout the mistake? I would really appreciate that.

 

[tiny-tim]

n∗(n−1)∗(n−2)∗...∗(n−i+1)(n-1)! = n!

with n = 12 and i = 5, this is 12*11*10*9*8*4*3*2*1, not 12!

(where did you get this formula from?)

instead of (n-1)!, you need … ? ​

 

[mindauggas]

with n = 12 and i = 5, this is 12*11*10*9*8*4*3*2*1, not 12!

(where did you get this formula from?)

instead of (n-1)!, you need … ? ​

I multiplied both sides of the original equation (Cin = (n∗(n−1)∗(n−2)∗...∗(n−i+1))/1∗2∗...∗i = n!/i!(n−i)!) by (n-1)!

 

[NascentOxygen]

This is how I got it:

n∗(n−1)∗(n−2)∗...∗(n−i+1)(n-1)! = n!

typo, should be . . . . . . . (n-i)!

 

[mindauggas]

typo, should be . . . . . . . (n-i)!

Thanks for point that out, I think tiny-tim was indicating that also.

So thank you guys, I got the insight by reversing the numerator:

(n-i)!*(n-i+1)*...*(n-2)*(n-1)*n = n!

because (n-i)! is 1*2*...*(n-i) it is now visible for me (some of you may hold that it was visible all along) that the left side is the same as n!

It is interesting how even an operation performed on a tautological statement (thus not changing the statement "essentially") has heuristic value.

Thank you all for your time

 

[mindauggas]

I didn't want to create a new thread so I ask here...

I want to prove by mathematical induction the following statement:

$\frac{1}{2}$+$\frac{2}{2^{2}}$+...+$\frac{n}{2^{n}}$=2-$\frac{n+2}{2^{n}}$

I formulate the induction step as follows:

$\frac{1}{2}$+$\frac{2}{2^{2}}$+...+$\frac{n}{2^{n}}$+$\frac{n+1}{2^{n+1}}$=2-$\frac{(n+1)+2}{2^{n+1}}$

Is this correct?

 

[FroChro]

Is this correct?

So far, it is. But the proof is not done yet.

It is interesting how even an operation performed on a tautological statement (thus not changing the statement "essentially") has heuristic value.

Well, I think the statement was changed quite essentially for example once you substituted expression/symbols n*(n-1)*...*1 for expression/symbol n!. It is something like turning the paper over to see what's on the other side, you didn't change paper "essentially", but you've done something, and it's of great importance you realize this.

 

[mindauggas]

I returned to this problem after some time, still can not find the solution.

I took the following steps:

Prove by mathematical induction (the hypothesis):

$\frac{1}{2}$+$\frac{2}{2^{2}}$+...+$\frac{n}{2^{n}}$=2-$\frac{n+2}{2^{n}}$

The induction step:

$\frac{1}{2}$+$\frac{2}{2^{2}}$+...+$\frac{n}{2^{n}}$+$\frac{n+1}{2^{n+1}}$=2-$\frac{(n+1)+2}{2^{n+1}}$

Now here I get a bit confused, because I wanted to write:

2-$\frac{n+2}{2^{n}}$+$\frac{n+1}{2^{n+1}}$=2-$\frac{(n+1)+2}{2^{n+1}}$

But is this logically consistent? Because I am assuming exactly the thing I'm trying to prove?

So the question is - can i do that?

 

[SammyS]

I didn't want to create a new thread so I ask here...

I want to prove by mathematical induction the following statement:

$\frac{1}{2}$+$\frac{2}{2^{2}}$+...+$\frac{n}{2^{n}}$=2-$\frac{n+2}{2^{n}}$

I formulate the induction step as follows:

$\frac{1}{2}$+$\frac{2}{2^{2}}$+...+$\frac{n}{2^{n}}$+$\frac{n+1}{2^{n+1}}$=2-$\frac{(n+1)+2}{2^{n+1}}$

Is this correct?

You assume that $\displaystyle \frac{1}{2}+\frac{2}{2^{2}}+\dots+\frac{n}{2^{n}}=2-\frac{n+2}{2^{n}}$ is true.

Now you must show from that assumption that the following is true: $\displaystyle \frac{1}{2}+\frac{2}{2^{2}}+\dots+\frac{n}{2^{n}}+\frac{n+1}{2^{n+1}}=2-\frac{(n+1)+2}{2^{n+1}}$

 

[mindauggas]

You assume that $\displaystyle \frac{1}{2}+\frac{2}{2^{2}}+\dots+\frac{n}{2^{n}}=2-\frac{n+2}{2^{n}}$ is true.

Now you must show from that assumption that the following is true: $\displaystyle \frac{1}{2}+\frac{2}{2^{2}}+\dots+\frac{n}{2^{n}}+\frac{n+1}{2^{n+1}}=2-\frac{(n+1)+2}{2^{n+1}}$

The question here was is my induction step correctly stated, it seems like it is.

Now the question is can i write:2-$\frac{n+2}{2^{n}}$+$\frac{n+1}{2^{n+1}}$=2-$\frac{(n+1)+2}{2^{n+1}}$

Thus assuming (it seems to me at least, though I'm not sure) the thing I'm trying to prove ...

 

[Bohrok]

You basically do "assume what you're trying to prove." You use this assumption
$\frac{1}{2}$+$\frac{2}{2^{2}}$+...+$\frac{n}{2^{n}}$=2-$\frac{n+2}{2^{n}}$

somewhere in the steps when you prove this
2-$\frac{n+2}{2^{n}}$+$\frac{n+1}{2^{n+1}}$=2-$\frac{(n+1)+2}{2^{n+1}}$

Combine the two fractions on the left and get them to look like the fraction on the right.

 

[vela]

Yeah, you don't really want to write that equality just yet. Instead, start with the lefthand side and turn it into the righthand side.
\begin{align*}
\frac{1}{2}+\frac{2}{2^{2}}+\cdots+\frac{n}{2^{n}}+\frac{n+1}{2^{n+1}} & = \left( \frac{1}{2}+\frac{2}{2^{2}}+\cdots+\frac{n}{2^{n}}\right) + \frac{n+1}{2^{n+1}} \\
& \vdots \\
& =2-\frac{(n+1)+2}{2^{n+1}}
\end{align*}
Use the induction hypothesis to simplify the quantity in the parentheses and then simplify.

 

[mindauggas]

Use the induction hypothesis to simplify the quantity in the parentheses and then simplify.

You mean as such?

2-$\frac{n+2}{2^{n}}$+$\frac{n+1}{2^{n+1}}$=2-$\frac{(n+1)+2}{2^{n+1}}$

 

[vela]

No, that's what you're trying to prove. (Or you need to show more steps.) The stuff in the parentheses is a sum of n terms. By assumption, you know what that equals.

 

[mindauggas]

No, that's what you're trying to prove. (Or you need to show more steps.) The stuff in the parentheses is a sum of n terms. By assumption, you know what that equals.

Well the stuff in the parentheses is this:

2-$\frac{n+2}{2^{n}}$

or is it not?

or are you trying to put across the idea that i should do this:

2-$\frac{(n+1)+2}{2^{n+1}}$-$\frac{n+1}{2^{n+1}}$

?

 

[FroChro]

Well the stuff in the parentheses is this:

2-$\frac{n+2}{2^{n}}$

or is it not?

Yes, it is.
The point is that you have to prove (to show) that it really is true that
$2-\frac{n+2}{2^{n}}$+$\frac{n+1}{2^{n+1}}$=2-$\frac{(n+1)+2}{2^{n+1}}\quad .$

Once you will show that right hand side is equal to left hand side you will show that if the assumption is true for n then it is true for n+1. So far, it is not obvious that equation written here is right. (Schematically, in this stage it is more like
$2-\frac{n+2}{2^{n}}$+$\frac{n+1}{2^{n+1}}$(?=?)2-$\frac{(n+1)+2}{2^{n+1}}\quad .$ )

 

[vela]

Well the stuff in the parentheses is this:

2-$\frac{n+2}{2^{n}}$

or is it not?

Yes, you're right. Sorry, I misread your post.

 

[mindauggas]

Yes, you're right. Sorry, I misread your post.

misread or didn't you actually helped me to solve the problem.

Previously I did it like this:

$2-\frac{n+2}{2^{n}}$+$\frac{n+1}{2^{n+1}}$=2-$\frac{(n+1)+2}{2^{n+1}}\quad .$

and tried to reduce the left hand side

doing it this way (much simpler):

$2-\frac{n+2}{2^{n}}$=2-$\frac{(n+1)+2}{2^{n+1}}\quad$-$\frac{n+1}{2^{n+1}}$

just did not occurred ... don't ask me why ... this is embarrassing

Thanks everyone.