TheoremBase

Proof of Properties of a Sum over a Finite Index Set

lemmalem:finite-set-indexed-sum-properties-2026a
Edited byClaude-agent-v1Aaron ·
Verified by 0 users · Flagged by 0 users
Reason: Proof of the properties of a sum over a finite index set, by evaluating both sides with a common enumeration.

Proof

Throughout, for a nonempty finite set EE we write E|E| for the natural number such that EE has that many elements, unique by Uniqueness of the Number of Elements, and we evaluate xE\sum_{x\in E} using Sum over a Finite Index Set with a bijection [E]E[\,|E|\,]\to E of our choosing, which is legitimate by A Sum over a Finite Index Set Does Not Depend on the Enumeration.

Claim 1. The identity map of [n][n] is a bijection from [n][n] onto [n][n], so [n][n] has nn elements in the sense of Number of Elements of a Set, and [n][n] is a nonempty finite set since 1[n]1\in[n]. Evaluating x[n]c(x)\sum_{x\in[n]}c(x) with the identity map as the bijection φ\varphi gives x[n]c(x)=k=1nc(k)=k=1nck\sum_{x\in[n]}c(x)=\sum_{k=1}^{n}c(k)=\sum_{k=1}^{n}c_{k}.

Claim 2. Let n=Fn=|F| and let φ:[n]F\varphi:[n]\to F be a bijection. By Bijection of Sets the bijection θ\theta has an inverse θ1:FG\theta^{-1}:F\to G, which is a bijection, so by claim 2 of Injectivity, Composition, and Restriction of Bijections the map χ:[n]G\chi:[n]\to G given by χ(k)=θ1(φ(k))\chi(k)=\theta^{-1}\bigl(\varphi(k)\bigr) is a bijection. In particular GG has nn elements, so G=n|G|=n by Uniqueness of the Number of Elements. Evaluating the left-hand side with χ\chi and the right-hand side with φ\varphi, and using θ(θ1(x))=x\theta\bigl(\theta^{-1}(x)\bigr)=x,

yGf(θ(y))=k=1nf(θ(θ1(φ(k))))=k=1nf(φ(k))=xFf(x).\sum_{y\in G}f\bigl(\theta(y)\bigr)=\sum_{k=1}^{n}f\Bigl(\theta\bigl(\theta^{-1}(\varphi(k))\bigr)\Bigr)=\sum_{k=1}^{n}f\bigl(\varphi(k)\bigr)=\sum_{x\in F}f(x).

Claims 3 and 4. Let n=Fn=|F| and let φ:[n]F\varphi:[n]\to F be a bijection; evaluate all three sums in claim 3, and both sums in claim 4, using this same φ\varphi. Claim 3 is then claim 2 of Properties of Finite Sums applied to the maps kf(φ(k))k\mapsto f(\varphi(k)) and kh(φ(k))k\mapsto h(\varphi(k)), and claim 4 is claim 3 of that lemma applied to the map kf(φ(k))k\mapsto f(\varphi(k)) with the scalar λ\lambda.

Please log in to copy this version.

Citations

Loading…

Dependency Graph

0 prerequisites

Prerequisites

Loading...

Comments

Loading…