1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of equality involving factorials

  1. Jun 28, 2011 #1
    Hello everyone
    1. The problem statement, all variables and given/known data
    i dont see a connection why Cin = [itex]\frac{(n*(n-1)*(n-2)*...*(n-i+1))}{1*2*...*i }[/itex] = [itex]\frac{n!}{i!(n-i)!}[/itex]

    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. jcsd
  3. Jun 28, 2011 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    welcome to pf!

    hello mindauggas! welcome to pf! :smile:

    what do you have to multiply the top by to get n! ? :wink:
     
  4. Jun 28, 2011 #3
    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
  5. Jun 28, 2011 #4
    Think of this You can write (expand) [tex]n![/tex] on the top as

    [tex] n(n-1)(n-2)...(n-i+1)(n-i)! [/tex]

    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
  6. Jun 28, 2011 #5

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You might find it easier to go the other way. Expand the factorials in
    [tex]\frac{n!}{i!(n-i)!}[/tex]
    and simplify. If using variables confuses you, it may help to try specific numbers for n and i to identify the pattern.
     
  7. Jun 29, 2011 #6
    Thank guys you for your help. I understood everything except one thing, this is what i did.

    Cin= [itex]\frac{(n∗(n−1)∗(n−2)∗...∗(n−i+1))(n-1)!}{i!}[/itex] = [itex]\frac{n!}{i!(n−i)!}[/itex]

    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?
     
  8. Jun 29, 2011 #7

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi mindauggas! :smile:
    (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? :confused:

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

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

    now that is 12! over what? :smile:
     
  9. Jun 29, 2011 #8
    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.
     
  10. Jun 29, 2011 #9

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

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

    (where did you get this formula from?)

    instead of (n-1)!, you need … ? :smile:
     
  11. Jun 29, 2011 #10
    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)!
     
  12. Jun 29, 2011 #11

    NascentOxygen

    User Avatar

    Staff: Mentor

    typo, should be . . . . . . . (n-i)!
     
    Last edited: Jun 29, 2011
  13. Jun 29, 2011 #12
    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 :smile:
     
  14. Jul 9, 2011 #13
    I didn't want to create a new thread so I ask here...

    I want to prove by mathematical induction the following statement:

    [itex]\frac{1}{2}[/itex]+[itex]\frac{2}{2^{2}}[/itex]+...+[itex]\frac{n}{2^{n}}[/itex]=2-[itex]\frac{n+2}{2^{n}}[/itex]

    I formulate the induction step as follows:

    [itex]\frac{1}{2}[/itex]+[itex]\frac{2}{2^{2}}[/itex]+...+[itex]\frac{n}{2^{n}}[/itex]+[itex]\frac{n+1}{2^{n+1}}[/itex]=2-[itex]\frac{(n+1)+2}{2^{n+1}}[/itex]

    Is this correct?
     
  15. Jul 9, 2011 #14
    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.
     
  16. Aug 6, 2011 #15
    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):

    [itex]\frac{1}{2}[/itex]+[itex]\frac{2}{2^{2}}[/itex]+...+[itex]\frac{n}{2^{n}}[/itex]=2-[itex]\frac{n+2}{2^{n}}[/itex]

    The induction step:

    [itex]\frac{1}{2}[/itex]+[itex]\frac{2}{2^{2}}[/itex]+...+[itex]\frac{n}{2^{n}}[/itex]+[itex]\frac{n+1}{2^{n+1}}[/itex]=2-[itex]\frac{(n+1)+2}{2^{n+1}}[/itex]

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

    2-[itex]\frac{n+2}{2^{n}}[/itex]+[itex]\frac{n+1}{2^{n+1}}[/itex]=2-[itex]\frac{(n+1)+2}{2^{n+1}}[/itex]

    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?
     
  17. Aug 6, 2011 #16

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    You assume that [itex]\displaystyle \frac{1}{2}+\frac{2}{2^{2}}+\dots+\frac{n}{2^{n}}=2-\frac{n+2}{2^{n}}[/itex] is true.

    Now you must show from that assumption that the following is true: [itex]\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}}[/itex]
     
  18. Aug 6, 2011 #17
    The question here was is my induction step correctly stated, it seems like it is.

    Now the question is can i write:


    2-[itex]\frac{n+2}{2^{n}}[/itex]+[itex]\frac{n+1}{2^{n+1}}[/itex]=2-[itex]\frac{(n+1)+2}{2^{n+1}}[/itex]

    Thus assuming (it seems to me at least, though i'm not sure) the thing i'm trying to prove ...
     
  19. Aug 6, 2011 #18
    You basically do "assume what you're trying to prove." You use this assumption
    [itex]\frac{1}{2}[/itex]+[itex]\frac{2}{2^{2}}[/itex]+...+[itex]\frac{n}{2^{n}}[/itex]=2-[itex]\frac{n+2}{2^{n}}[/itex]

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

    Combine the two fractions on the left and get them to look like the fraction on the right.
     
  20. Aug 6, 2011 #19

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    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.
     
  21. Aug 6, 2011 #20
    You mean as such?

    2-[itex]\frac{n+2}{2^{n}}[/itex]+[itex]\frac{n+1}{2^{n+1}}[/itex]=2-[itex]\frac{(n+1)+2}{2^{n+1}}[/itex]
     
    Last edited: Aug 6, 2011
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof of equality involving factorials
Loading...