Review on Proofs

Proof (contrapositive). Since every integer is even or odd and not both, the contrapositive is: for every integer $n$, if $n$ is odd, then $n^2$ is odd. Let $n$ be an arbitrary odd integer, so $n = 2k + 1$ for some integer $k$. Then $$n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 ,$$ and $2k^2 + 2k$ is an integer, so $n^2$ is odd. ∎

Proof (contrapositive). By De Morgan's law, the negation of “$a$ is odd or $b$ is odd” is “$a$ is not odd and $b$ is not odd”, that is, $a$ and $b$ are both even. So the contrapositive is: if $a$ and $b$ are both even, then $a + b$ is even (that is, not odd). Let $a$ and $b$ be arbitrary even integers, say $a = 2k$ and $b = 2\ell$ with $k, \ell$ integers. Then $a + b = 2(k + \ell)$, and $k + \ell$ is an integer, so $a + b$ is even. ∎

Proof (contradiction). Suppose, for contradiction, that some rational number has square $2$. Write it as $a/b$ with $a, b$ integers, $b \neq 0$, in lowest terms. Then $a^2 = 2b^2$, so $a^2$ is even, and by Example 1, $a$ is even: $a = 2k$ for some integer $k$. Then $4k^2 = 2b^2$, so $b^2 = 2k^2$ is even, and by Example 1 again, $b$ is even. So $2$ divides both $a$ and $b$, which contradicts that $a/b$ is in lowest terms. ∎

Proof (contradiction). Suppose, for contradiction, that more than $n$ pigeons are placed in $n$ holes, each in exactly one hole, and that every hole holds at most one pigeon. Let $p_i$ be the number of pigeons in hole $i$. Then the number of pigeons is $$p_1 + p_2 + \cdots + p_n \;\le\; 1 + 1 + \cdots + 1 \;=\; n ,$$ which contradicts that there are more than $n$. ∎

Proof (induction on $n$).

Base case. For $n = 1$, both sides equal $1$.

Inductive hypothesis. Let $k \ge 1$ be an arbitrary integer, and assume $1 + 3 + \cdots + (2k - 1) = k^2$.

Inductive step. The sum of the first $k + 1$ positive odd numbers is the sum of the first $k$ plus $2(k + 1) - 1 = 2k + 1$. By the inductive hypothesis, $$1 + 3 + \cdots + (2k - 1) + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2 .$$ By induction, the claim holds for every integer $n \ge 1$. ∎

Proof (induction on $n$).

Base case. $4^0 - 1 = 0 = 3 \cdot 0$.

Inductive hypothesis. Let $k \ge 0$ be an arbitrary integer, and assume $3 \mid (4^k - 1)$: $4^k - 1 = 3a$ for some integer $a$.

Inductive step. By the inductive hypothesis, $$4^{k+1} - 1 = 4(4^k - 1) + 3 = 4 \cdot 3a + 3 = 3(4a + 1),$$ and $4a + 1$ is an integer, so $3 \mid (4^{k+1} - 1)$. By induction, the claim holds for every integer $n \ge 0$. ∎

Proof (induction on $n$).

Base case. $2^5 = 32 > 25 = 5^2$.

Inductive hypothesis. Let $k \ge 5$ be an arbitrary integer, and assume $2^k > k^2$.

Inductive step. Multiplying the inductive hypothesis by $2$ gives $2^{k+1} > 2k^2$. Since $k - 1 \ge 4$, we have $2k^2 - (k+1)^2 = (k - 1)^2 - 2 \ge 14 > 0$. So $2^{k+1} > 2k^2 > (k + 1)^2$. By induction, the claim holds for every integer $n \ge 5$. ∎

Proof (strong induction on $n$).

Base cases. $F_1 = 1 < 2$ and $F_2 = 1 < 4$.

Inductive hypothesis. Let $k \ge 2$ be an arbitrary integer, and assume $F_j < 2^j$ for every integer $j$ with $1 \le j \le k$.

Inductive step. Since $k + 1 \ge 3$, $F_{k+1} = F_k + F_{k-1}$, and $1 \le k - 1 < k$. By the inductive hypothesis, $$F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} < 2^k + 2^k = 2^{k+1} .$$ By strong induction, the claim holds for every integer $n \ge 1$. ∎

Proof (strong induction on $n$).

Base case. $1 = 2^0$.

Inductive hypothesis. Let $k \ge 1$ be an arbitrary integer, and assume every integer $j$ with $1 \le j \le k$ is a sum of distinct powers of $2$.

Inductive step. Let $n = k + 1$. Since $n$ is even or odd, $n = 2m$ or $n = 2m + 1$ for some integer $m$, and in either case $n - 1 \le 2m \le n$. So $2m \ge k \ge 1$, which gives $m \ge 1$, and $m \le (k + 1)/2 \le k$. By the inductive hypothesis, $m = 2^{a_1} + \cdots + 2^{a_r}$ with distinct integers $a_1, \dots, a_r \ge 0$, so $$2m = 2^{a_1 + 1} + \cdots + 2^{a_r + 1}, \qquad 2m + 1 = 2^{a_1 + 1} + \cdots + 2^{a_r + 1} + 2^0 .$$ The exponents $a_1 + 1, \dots, a_r + 1$ are distinct and at least $1$, so in both sums the exponents are distinct, and $n$ is one of the two. By strong induction, the claim holds for every integer $n \ge 1$. ∎

Proof (strong induction on the number of edges). Let $G$ be a connected graph in which every vertex has even degree, and let $m$ be the number of edges of $G$.

Base case. $m = 0$. $G$ has at least one vertex, and it cannot have two different vertices $u$ and $w$: a walk from $u$ to $w$ would have to use an edge. So $G$ has exactly one vertex $v$. The walk consisting of $v$ alone is closed, and it uses every edge of $G$ (there are none) exactly once, so it is an Euler tour.

Inductive hypothesis. Now let $m \ge 1$, and assume that every connected graph with fewer than $m$ edges in which every vertex has even degree has an Euler tour.

Inductive step. We build an Euler tour of $G$.

(1) A closed walk. Pick a vertex $v$ with an edge, and walk from $v$ along unused edges until the current vertex has none left; this stops, as there are finitely many edges. If it stopped at some $x \neq v$, then each earlier visit to $x$ used two edges at $x$ and the last arrival one more, an odd number in all; as $\deg(x)$ is even, some edge at $x$ would still be unused. So the walk ends at $v$: it is a closed walk $C = c_0, c_1, \dots, c_\ell$ with $c_0 = c_\ell = v$ and $\ell \ge 1$, using no edge twice.

(2) The pieces. Let $G'$ be the graph with the vertices of $G$ and the edges that $C$ does not use; it has $m - \ell < m$ edges. $C$ uses two edges at $c_i$ for each $0 < i < \ell$, and the first and last edges at $v$, so every vertex has even degree in $G'$. Let $H$ be a component of $G'$, with the edges of $G'$ between its vertices. Every edge of $G'$ at a vertex of $H$ lies in $H$, so the degrees in $H$ are those in $G'$, which are even; two vertices of $H$ are joined by a walk in $G'$, which stays in $H$, so $H$ is connected; and $H$ has fewer than $m$ edges. By the inductive hypothesis, $H$ has an Euler tour.

(3) Each piece meets $C$. Let $u$ be a vertex of a component $H$, and take a walk in $G$ from $u$ to $v$. Let $w$ be its first vertex on $C$. Each edge of the walk before $w$ has an endpoint off $C$, while an edge that $C$ uses has both endpoints on $C$; so $C$ does not use it, and these edges are in $G'$. So $w$ lies in $H$.

(4) Splicing. For each component $H$, let $i_H$ be the least $i$ with $c_i$ in $H$. If $H$ has no edge, then $H$ is the single vertex $c_{i_H}$, and its tour is that vertex alone. Otherwise $H$ is connected with at least two vertices, so every vertex of $H$ has an edge, and $c_{i_H}$ lies on the tour $w_0, w_1, \dots, w_s$ of $H$ (where $w_s = w_0$): say $c_{i_H} = w_j$ with $0 \le j < s$. Then $w_j, \dots, w_s, w_1, \dots, w_j$ is a tour of $H$ that starts and ends at $c_{i_H}$ (if $j = 0$, keep the tour as it is). Follow $C$, and at each $c_i$ go round the tours of all components $H$ with $i_H = i$. The result is a closed walk. Every edge of $G$ is used by $C$ or lies in exactly one component, $C$ and each tour use their edges once, and each tour is inserted once; so the walk uses every edge of $G$ exactly once: it is an Euler tour of $G$.

By strong induction on the number of edges, every connected graph in which every vertex has even degree has an Euler tour. ∎