# Proof of equality involving factorials

1. Jun 28, 2011

### mindauggas

Hello everyone
1. The problem statement, all variables and given/known data
i dont see a connection why Cin = $\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?

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

Last edited: Jun 28, 2011
2. Jun 28, 2011

### tiny-tim

welcome to pf!

hello mindauggas! welcome to pf!

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

3. Jun 28, 2011

### 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?

Last edited: Jun 28, 2011
4. Jun 28, 2011

### 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 ?

Last edited: Jun 28, 2011
5. Jun 28, 2011

### vela

Staff Emeritus
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.

6. Jun 29, 2011

### mindauggas

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

Cin= $\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?

7. Jun 29, 2011

### tiny-tim

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?

8. Jun 29, 2011

### mindauggas

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.

9. Jun 29, 2011

### tiny-tim

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 … ?

10. Jun 29, 2011

### mindauggas

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)!

11. Jun 29, 2011

### Staff: Mentor

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

Last edited: Jun 29, 2011
12. Jun 29, 2011

### mindauggas

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

13. Jul 9, 2011

### 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?

14. Jul 9, 2011

### FroChro

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

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.

15. Aug 6, 2011

### 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?

16. Aug 6, 2011

### SammyS

Staff Emeritus
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}}$

17. Aug 6, 2011

### mindauggas

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

18. Aug 6, 2011

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

19. Aug 6, 2011

### vela

Staff Emeritus
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.

20. Aug 6, 2011

### mindauggas

You mean as such?

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

Last edited: Aug 6, 2011