A proof for summations?

Prove that, for any sequence a_ij, it holds:

∑{i=0,n} ∑{j=0,i} a_ij = ∑{j=0,n} ∑{i=j,n} a_ij

[a_ij = a sub i,j ]

Explain.

Thanks.

1 Answer

Relevance
  • Eugene
    Lv 7
    6 years ago
    Favorite Answer

    Let X = {(i,j): 0 ≤ i ≤ n, 0 ≤ j ≤ i}. The left-hand side of the identity can be written

    (*) ∑ ∑{0 ≤ i ≤ n, 0 ≤ j ≤ n} a_ij b_ij,

    where b_ij = 1 if (i,j) is in X and b_ij = 0 otherwise. As (i,j) ranges over X, i ranges from j to n as j ranges from 0 to n. So X = {(i,j): 0 ≤ i ≤ n, j ≤ i ≤ n}. Then (*) becomes

    ∑{0 ≤ j ≤ n} ∑{j ≤ i ≤ n} a_ij,

    which is the right-hand side of the identity.

Still have questions? Get your answers by asking now.