Evaluate ∑ k ≥ 0 ( − 1 ) k ( n k ) 2 using sign reversing involutions. When n is odd, the problem is trivial : let [ n ] = { 1 , 2 , … , n } consider all pairs of subsets { ( A , B ) ∈ 2 [ n ] × 2 [ n ] : | A | = | B | }, and ( A , B ) has sign ( − 1 ) | A | and the sign-reversing involution is ( A , B ) → ( [ n ] − A , [ n ] − B ). Any hints on how to approach this problem for even n will be appreciated.

Question

Evaluate       ∑          k      ≥      0        (  −  1      )    k                            (                    n        k                          )              2   using sign reversing involutions. When   n is odd, the problem is trivial : let   [  n  ]  =  {  1  ,  2  ,  …  ,  n  } consider all pairs of subsets   {  (  A  ,  B  )  ∈      2          [      n      ]        ×      2          [      n      ]        :  |  A  |  =  |  B  |  }, and   (  A  ,  B  ) has sign   (  −  1      )              |      A          |       and the sign-reversing involution is   (  A  ,  B  )  →  (  [  n  ]  −  A  ,  [  n  ]  −  B  ). Any hints on how to approach this problem for even   n will be appreciated.

flonsHaroDolalv · Accepted Answer

Consider the set of pairs   (  A  ,  B  ) of subsets of   {  1  ,  …  ,  n  } such that   |  A  |  +  |  B  |  =  n with weight   (  −  1      )              |      A          |      . The exceptional pairs where the involution is not defined are those where   A  =  B. For each other pair   (  A  ,  B  ) take the smallest element of the symmetric difference of   A and   B and move it from one set to the other. The symmetric difference of the two new sets is the same, so this is an involution, and it is weight-reversing.

istremage8o · Accepted Answer

lox

Evaluate <munder> ∑ k ≥ 0

Answered question

Answer & Explanation

New Questions in Precalculus