Let m , n ≥ 0 be two integers. Prove that ∑ k = m n ( − 1 ) k − m ( k m ) ( n k ) = δ m n where δ m n defined by δ m n = { 1 , if m = n ; 0 , if m ≠ n

Question

Let   m  ,  n  ≥  0 be two integers. Prove that      ∑          k      =      m        n    (  −  1      )          k      −      m                      (              k      m                  )                      (              n      k                  )        =      δ          m      n      where       δ          m      n       defined by       δ          m      n        =      {                            1          ,                          if           m          =          n          ;                                      0          ,                          if           m          ≠          n

duhovitozywpv · Accepted Answer

This follows easily from the Multinomial Theorem:  1  =      1    n    =  (  1  −  x  +  x      )    n    =      ∑          a      +      b      +      c      =      n                      (              n              a        ,        b        ,        c                        )            1    a    ⋅  (  −  x      )    b    ⋅      x    c    =      ∑          m      =      0          n        ∑          k      =      m          n                  (              n              m        ,        k        −        m        ,        n        −        k                        )            1      m    ⋅  (  −  x      )          k      −      m        ⋅      x          n      −      k        =      ∑          m      =      0          n        [          ∑              k        =        m                n        (    −    1          )              k        −        m                                    (                    k        m                          )                                    (                    n        k                          )              ]        x          n      −      m      Comparing coefficients now gives the result immediately.

Kaitlyn Higgins · Accepted Answer

Here&#039;s another way to look at Aryabhata&#039;s proof: the sum counts all the partitions of   [  n  ] into three sets   A  ,  B  ,  C satisfying   |  C  |  =  m, weighted according to   (  −  1      )              |      A          |      . The identity just says that if   n  ≠  m, the number of partitions with   |  A  | even is the same as those with   |  A  | odd.The latter fact is proved by the following sign-changing involution: pick the first element which is not in   C (there must be one since   n  ≠  m), and flip it from   A to   B or vice versa.

Let m , n ≥ 0 be two integers. Prove that <munderover> ∑

Answered question

Answer & Explanation

New Questions in Precalculus