The relation is reflexive because $a-a=2\cdot 0$. It is symmetric because $a-b=2k$ implies $b-a=2(-k)$. It is transitive because $a-b=2k$ and $b-c=2\ell$ imply $a-c=2(k+\ell )$. It is therefore an equivalence relation, namely congruence modulo an integer for modulus two. Its two equivalence classes consist of the even integers and the odd integers.

Use mathematical induction with the defining Fibonacci recurrence. Both identities hold at $n=0$: their two sides are zero. If the first holds at $n$, thenIf the second holds at $n$, thenEach inductive hypothesis therefore advances to $n+1$.

Partition the power set into disjoint classes according to subset size. The class of size-$i$ subsets has cardinality $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, while the whole power set has cardinality $2^n$. Counting every subset once givesThis is also the binomial theorem evaluated at $1+1$, but the counting proof follows directly from the earlier parts.

There are $n(n-1)\cdots (n-k+1)=n!/(n-k)!$ ordered selections of $k$ distinct elements. Every size-$k$ subset appears in exactly $k!$ orders, giving the binomial coefficientFor $k=0$, both the empty selection and $0!$ contribute one.

List the $n$ elements of the finite set $A$. A subset is determined by $n$ membership decisions, each with two possibilities. This is a bijection from the power set to the set $\{0,1{\}}^n$, soThe empty set case is included: its power set contains the single empty subset.

For every $x\in \mathbb{R}$, the definition of function composition givesThe functions agree at every argument, so function extensionality proves the associative property of function composition.

Function composition is not always commutative. The reversed function composition may be undefined when the necessary domain of a function and codomain do not match. A counterexample using functions $\mathbb{R}\to \mathbb{R}$ avoids that issue: let $f(x)=x+1$ and $g(x)=2x$. ThenBoth function compositions exist, and their values differ at every real $x$.

Apply the two identities already proved with $A=\mathcal{U}$. Every $B_i$ is a subset of the common universe, and a complement is the set difference from that universe. ThereforeReplacing each set difference from $\mathcal{U}$ by its complement notation gives the claimed finite forms of De Morgan's laws.

Prove both identities by mathematical induction. The base case $n=2$ is the two-set form of De Morgan's laws. For the union identity, suppose the result holds for $n$. Applying the two-set identity and then the inductive hypothesis givesFor the intersection identity, the corresponding step isThese close the two inductions.

By De Morgan's laws, taking a set difference from a union requires exclusion from both sets, while taking a set difference from an intersection requires exclusion from at least one:For example, $x$ belongs to the first left-hand side precisely when $x\in A$, $x\notin B$ and $x\notin C$; these are exactly the membership conditions on the first right-hand side. For the second identity, replace the two exclusions by their logical disjunction.