Dr D
Lv 7
Dr D asked in Science & MathematicsMathematics · 1 decade ago

Can anyone prove that ∑ (-1)^i * nCi * (k – i)^n = n!?

Prove that


∑ (-1)^i * nCi * (k – i)^n = n!


where i, n, k Є Z+


Sorry that should be

i, n, k Є Z

Update 2:

Test it for yourself and see if the result is independent of k.

Update 3:

Yes nCi is the combination formula.

For n=1, k=10, LHS = 10^1 - 9^1 = 1

For n=2, k=10, LHS = 10^2 - 2*9^2 + 8^2 = 2

Update 4:

For n=0, LHS = 1

For n=3, k= -1, LHS = (-1)^3 - 3*(-2)^3 + 3*(-3)^3 - (-4)^3 = 6

Update 5:

Obviously I formulated this question out of the one Zanti referred to, but can anyone do this using induction or some other method that does not derive from successive differences?

Update 6:

NO I haven't found a way to do it. If I had, I would have used it to answer the other question.

5 Answers

  • Anonymous
    1 decade ago
    Favorite Answer

    Sure, no sweat. It follows directly from the answer to this question:


    * * * * *

    OK, I'll try to work out the details...

    We know from the proofs given in the answer to the above question that taking the differences of x^n eventually gets us to a row of n! constants. Also, if we start taking differences from the top, we see this:

    Row 1: 1^n, 2^n, 3^n, 4^n, ...

    Row 2: (2^n - 1^n), (3^n - 2^n), (4^n - 3^n), etc. The ith term is (i+1)^n - i^n.

    Row 3: (3^n - 2*2^n + 1^n), (4^n - 2*3^n + 2^n), (5^n - 2*4^n + 3^n), etc. The ith term is (i+2)^n - 2(i+1)^n + i^n.

    Row 4: (4^n - 3*3^n + 3*2^n - 1^n), (5^n - 3*4^n + 3*3^n - 2^n), etc. The ith term is (i+3)^n - 3(i+2)^n + 3(i+1)^n - i^n.

    The pattern is apparent that for row n+1, the ith term is (n+i)^n - nC1 * (n+i-1)^n + nC2 * (n+i-2)^n - nC3 * (n+i-3)^n + ... However, we also know from the previous question that row n+1 is the row of constants for x^n. Making the substitution k = n+i and writing everything as a summation brings us to your formula - and, interestingly, the value of k is irrelevant, so long as k is an integer.

    * * * * *

    Hmmm... trying to get this answer directly, rather than deriving the formula from a result we know HAS to be true, is definitely not easy. So, Doctor, are you saying you found a way to do this?

    • Log in to reply to the answers
  • Ben
    Lv 6
    1 decade ago

    I haven't managed to get something really nice yet, but I'll keep trying. In the meantime, I thought I would post up some of the ideas I've had:

    We can't do induction straight-away on this, at least not easily, since the summation will change inherently with the (k-i)^n term and the nCi (i.e., we can't just add a new term to the sum and be nearly finished).

    If we expand out the nCi, we can simply show that the sum of [(-1)^i*(k-i)^n] / [(n-1)!*i!] =1.

    I'll be back later...

    EDIT: I'm beginning to strongly suspect that this is beyond my abilities. I'll keep working on it, but I don't bet I'll get any further toward a solution. One note, the value of k is restricted between 1 and n, correct? Also, I started trying to expand the factorial into a horrible-looking "polynomial" (I've tried this before, but had more success just now); unfortunately, for the work, it didn't get me closer to a solution for this.

    • Log in to reply to the answers
  • rrsvvc
    Lv 4
    1 decade ago

    Sorry, but I'm not understanding this too well.

    Ci is C sub i or C times i or ?

    In any case, this doesn't work for n=0 since 0! =1 and the left side is 0. For n = 1, I get for the left side - C1(k - 1) which doesn't look like 1 to me.

    • Log in to reply to the answers
  • Anonymous
    1 decade ago

    ♠ n=2, s2 = x^2 –2*(x-1)^2 +(x-2)^2 = 2;

    and ds2/dx = 2x -4(x-1) +2(x-2) =0;

    s3=x^3 –3(x-1)^3 +3(x-2)^3 +(x-3)^3;

    s’3 = 3(x^2 –3(x-1)^2 +3(x-2)^2 –(x-3)^2) =

    = 3(s2 –(x-1)^2 +2(x-2)^2 –(x-3)^2) =

    = 3(s2-s2)=0;

    s(n+1,x) = ∑ (-1)^j *c(n+1,j)*(x-j)^(n+1), {j=0,n+1};

    s’(n+1,x) = (n+1)∑ (-1)^j *c(n+1,j)*(x-j)^n, {j=0,n+1};

    recall c(n,j) +c(n,j+1) =c(n+1,j+1);

    Guys do you still surrender?

    • Log in to reply to the answers
  • What do you think of the answers? You can sign in to give your opinion on the answer.
  • Anonymous
    1 decade ago

    omg yeah ttly ok so c=p*4+17 so that mean xy=nki and (k-i)4=n*2 and i=0 and so 2n*i=0


    • Log in to reply to the answers
Still have questions? Get answers by asking now.