Proof of a combination identity: ∑ j = 0 n ( − 1 ) j ( n j ) ( 1 − j n ) n = n ! n n

Question

Proof of a combination identity:       ∑          j      =      0        n        (    −    1          )      j                                            (                                                n                                j                                                )                                              (        1        −                  j          n                )            n        =            n      !              n      n

Kaiden Stevens · Accepted Answer

Start with      ∑          j      =      0              n        (  −  1      )    j                      (                    n      j                      )              (  1  +  x      )          n      −      j        =      x    n  which follows readily from the binomial theorem.Now differentiate, and multiply by       (    1    +    x    )  . Repeat this       n   times and set       x    =    0  .Notice that the constant term of the resulting polynomial on the right side is       n    !  .You can prove by induction that the lowest degree of       x   that appears on the right side after       k   steps   0  &amp;lt;      k    ≤    n   is             x              n        −        k             and has the coefficient       n    (    n    −    1    )    …    (    n    −    k    +    1    )  .This gives us the set of identities      ∑          j      =      0              n        (  −  1      )    j                      (                    n      j                      )              (  n  −  j      )          k        =  0  ,        0  ≤  k  &amp;lt;  n      ∑          j      =      0              n        (  −  1      )    j                      (                    n      j                      )              (  n  −  j      )          n        =  n  !

furajat4h · Accepted Answer

Lemma: Let   f  (  j  )  =      ∑          k      =      0        n        f    k        j    k   be a degree   n polynomial. Claim that       ∑          j      =      0              n        (  −  1      )    j                      (                    n      j                      )              f  (  j  )  =  n  !      f    n  .Proof: For any polynomial   g, define   Δ  (  g  ) to be the polynomial   Δ  (  g  )  Δ  (  g  )  (  j  )  =  g  (  j  )  −  g  (  j  +  1  ). Observe that, if   g is a polynomial with leading term   a      x    d    +  ⋯, then   Δ  (  g  ) is a polynomial with leading term   −  d  a      x          d      −      1        +  ⋯. In particular, if   f is as in the statement of the lemma, then       Δ    n    (  f  ) is the constant   (  −  1      )    n    n  !      f    n  . The sum in question is       Δ    n    (  f  ) evaluated at   0. QEDNow, apply the lemma to   f  (  j  )  =  (  1  −  j      /    n      )    n  .

Proof of a combination identity: ∑_(j=0)^n (−1)^j (n j)(1−j/n)^n=(n!)/(n^n)

Answered question

Answer & Explanation

New Questions in Precalculus