1. Not finding help here? Sign up for a free 30min 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!

Prove the equation

  1. Nov 6, 2016 #1
    1. The problem statement, all variables and given/known data
    Using the Newton's binomial, prove that
    ΣC(2+k,4) = (n+3,4), k=0,n

    2. Relevant equations
    (1+x)^n + (1+x)^m = (1+x)^(n+m)
    r≤min(m,n) => ΣC(n,k) * C(m,r-k) = C(n+m,k

    3. The attempt at a solution
    At first, I tried to see that this equation is correct with an example, n=3. But for the left side I get --- CC2,4)+C(3,4)+C(4,4)+C(5,4) = 6
    And for the right side --- C(6,4)=C(6,2)=15
    Maybe this is not a part of the process of proving but why is this happening?

    And please provide me with some guidance on how to think to prove this
     
  2. jcsd
  3. Nov 6, 2016 #2

    fresh_42

    Staff: Mentor

    It is always a good idea to check those formulas with small values. It might not only point to errors, it also might give you an idea how to prove them.
    Also, what I don't get is, why does the sum start at ##k=0## instead of ##k=2##? And isn't the case ##n=1## already wrong?

    So please check, if you got it right or if (at least me) has made a mistake as I took it for ##\sum_{k=0}^n \binom{2+k}{4}=\binom{n+3}{4} ##
     
  4. Nov 6, 2016 #3
    Well... With some quick googling I found a proof of Newton's binomial formula using proof by induction. Proof was from university of Helsinki (so the math research paper was in Finnish language)
    http://www.helsinki.fi/~koskenoj/alg1/binomikaava.pdf

    I'm not very good at proving in maths myself but that proof by induction could be one style of proof to go for...
     
  5. Nov 6, 2016 #4
    in the exercise k is from 0 to n, but the values 0 and 1 are useless because C(2,4) and C(3,4) are both 0. and yeah, n=1 is wrong too. so this equation is not correct?
     
  6. Nov 6, 2016 #5

    fresh_42

    Staff: Mentor

    At least not for all ##n##, maybe for some, but I doubt it. Calculating it for a few small ##n## I assume some patterns. The LHS looks like it always has a remainder ##1## on a division by ##5## and the RHS is divisible by ##5##. And the LHS is always the sum of both sides from the previous one.
     
  7. Nov 6, 2016 #6
    I just noticed that, that's interestingly true. I calculated both sides for a few n but they never get equal.
     
  8. Nov 6, 2016 #7

    fresh_42

    Staff: Mentor

    If you like to practice, you could prove my three claims and that the term on the right is always greater than the sum on the left.
     
  9. Nov 10, 2016 #8
    So, if it's

    sum of C(2+m,2) = C(n+3,3), m=0,n

    We have a formula:

    sum of C(k+m,k) = C(k+1+n,k+1)

    Is there a way to prove this?
     
  10. Nov 10, 2016 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Indeed.
    You could get a clue by writing out a few rows of Pascal's triangle. The sum consists of adding terms parallel to the right hand side, starting with a 1 at the top. Call that A. The next term in the sum is the one below and right of it. Call that B. Note that the term below and left of A (call that C) is also a 1, so adding A and B gives the same as adding C and B.
    What do you know about the sum of two adjacent terms in the same row, as B and C are?
     
  11. Nov 10, 2016 #10

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You can use the following facts from generating function theory:
    (1) Newton's binomial theorem (not the elementary binomial theorem!) gives
    $$(1-z)^{-p} = \sum_{k=0}^{\infty} {-p \choose k} (-z)^k, $$
    where for integer ##p > 0## we have
    $${ -p \choose k} = \frac{(-p)(p-1) \cdots (-p-k+1)}{k!} = (-1)^k {p+k-1 \choose k}$$.
    Thus
    $$ (1-z)^{-p} = \sum_{k=0}^{\infty} {p+k-1 \choose k} z^k, $$
    for integer ##p > 0##.

    (2) If ##A(z) = \sum_{k=0}^{\infty} a_k z^k##, then
    $$\frac{A(z)}{1-z} = \sum_{k=0}^{\infty} \left( \sum_{j=0}^k a_j \right) z^k .$$
    Apply this to ##A(z) = (1-z)^{-p}##.
     
  12. Nov 11, 2016 #11
    Starting row count from 0, on the nth row the sum of two adjacent terms is C(n,k) + C(n,k+1). I see similarities to the formula but there on the left side we have a sum of choosing k elements, whereas here this formula is the sum which consists of choosing k elements then k+1 elements
     
  13. Nov 11, 2016 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Start with an (n,0) term and add it to the (n+1,1) term. (n,0) and (n+1,0) are both 1, so this is the same as adding (n+1,0) and (n+1,1), which of course produces (n+2,1). Now add in the (n+2,2), and so forth.
     
  14. Nov 12, 2016 #13
    I did that, but I don't get to the proving part
     
  15. Nov 12, 2016 #14

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Use what you discovered from that to set up an inductive hypothesis and show that it is sustained.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prove the equation
  1. Prove the equation (Replies: 1)

  2. Proving a equation (Replies: 13)

Loading...