Alternating Subset Weights

S = {1,2,...,2013}. Find the sum of w(A) over every subset A ⊆ S.

Problem

A = {a₁ < a₂ < ... < aₖ}

w(A) = a₁ − a₂ + a₃ − a₄ + ...

Suppose a subset contains j. Its sign depends on how many selected numbers are smaller than j.

sign(j) = (−1)^{# selected elements below j}

Example: if two selected elements occur before j, then j is the third element of the subset and receives a + sign.

Choose j:

The total coefficient of j is

Σ_{B⊆{1,...,j−1}} (−1)^|B|

↓

(1 − 1)^j−1

↓

0 if j > 1

So every number 2,3,...,2013 has total contribution zero.

There are no smaller numbers than 1.

Therefore whenever a subset contains 1, it is always the first element:

The remaining 2012 elements can independently be included or excluded.

# subsets containing 1 = 2²⁰¹²

Only 1 survives
      contribution(1)
      =
      1 × 22012
    

      ∑A⊆S w(A) = 22012
    

Instead of considering all 2²⁰¹³ subsets, ask:

"What is the total coefficient of each number j?"

For every j > 1, toggle one smaller element. This changes j's position from odd to even, or even to odd:

+j ↔ −j

Thus they cancel pairwise. The number 1 has no smaller element available to toggle, so it is the only survivor.