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

Question

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

where i, n, k Є Z+

Sorry that should be
i, n, k Є Z

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

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

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

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?

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

Answer 1

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

http://answers.yahoo.com/question/index;_ylt=AuJIljKv2tzUvBVqgWy0DT3sy6IX;_ylv=3?qid=20071022082605AAjvuNi

* * * * *

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?

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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
=]