Proof Techniques

Induction is the well-ordering principle in disguise: if $P$ failed somewhere, take the least failure $m$; it is not $n_0$ by the base case, and $P$ holds below $m$, so the step gives $P(m)$ — contradiction. Strengthening sounds paradoxical (proving more is easier) but it is the usual reason an induction closes: the statement you want to prove is often too weak to be its own inductive hypothesis, as in Example 2, where “$< 2$” cannot be carried from $n$ to $n + 1$ but “$\le 2 - \tfrac1n$” can.

Step 1 — base case $n = 1$: a $2\times2$ board minus one cell is an L-tromino.

Step 2 — step: split the $2^{n+1}\times2^{n+1}$ board into four $2^n\times2^n$ quarters. The removed cell lies in one of them. Place one L-tromino at the center, covering the three central cells of the other three quarters.

Step 3 — now each quarter has exactly one cell removed or covered, and by the inductive hypothesis each can be tiled. $\blacksquare$ (The number of tiles is $\tfrac{4^n - 1}{3}$, an integer since $4 \equiv 1 \pmod 3$; for the $8\times8$ board, $21$.)

How to find it. The statement “any cell removed” is what makes the induction work: the central tromino creates three new holes in arbitrary positions of the quarters, and only the strong form covers them.

Step 1 — the direct induction fails: from $s_n < 2$ nothing prevents $s_{n+1} = s_n + \tfrac1{(n+1)^2}$ from exceeding $2$.

Step 2 — prove the stronger $s_n \le 2 - \tfrac1n$. Base: $s_1 = 1 = 2 - 1$. Step: $s_{n+1} \le 2 - \tfrac1n + \tfrac1{(n+1)^2}$, and this is at most $2 - \tfrac1{n+1}$ because $\tfrac1n - \tfrac1{n+1} = \tfrac1{n(n+1)} \ge \tfrac1{(n+1)^2}$.

Step 3 — so $s_n \le 2 - \tfrac1n < 2$. $\blacksquare$

How to find it. Ask what bound on $s_n$ would leave exactly enough room for the next term: you need $b_{n+1} - b_n \ge \tfrac1{(n+1)^2}$, and the telescoping $\tfrac1n - \tfrac1{n+1}$ is the natural candidate.

Step 1 — a lemma, by induction on $k$: a sum of distinct non-consecutive terms with largest term $F_k$ is less than $F_{k+1}$. For $k = 1, 2$ it is $1 < 2$ and $2 < 3$. In general the rest of the sum uses terms up to $F_{k-2}$, so by induction it is less than $F_{k-1}$, and the whole is less than $F_k + F_{k-1} = F_{k+1}$.

Step 2 — existence, by strong induction on $n$. Let $F_k$ be the largest term $\le n$. If $n = F_k$ we are done. Otherwise $0 < n - F_k < F_{k+1} - F_k = F_{k-1}$, so by the inductive hypothesis $n - F_k$ has a representation, which uses only terms below $F_{k-1}$ — non-consecutive with $F_k$.

Step 3 — uniqueness: in any representation of $n$ the largest term must be the $F_k$ of

Step 2 — a smaller largest term $F_j$ ($j < k$) gives a total below $F_{j+1} \le F_k \le n$ by the lemma. Remove $F_k$ and apply strong induction to $n - F_k$. $\blacksquare$ Example: $100 = 89 + 8 + 3$.

How to find it. Greedy (take the largest term) is the natural construction; the lemma is the precise statement that greedy is forced, and it is what makes both existence and uniqueness go through.

The two phrasings are the same argument: the set of values of the measure over all solutions, if nonempty, has a least element by well-ordering, and the descent step produces something smaller in the same set. What must be checked is that the new object really is a solution of the same equation (or of an equation covered by the same argument) and that the measure really decreases. Divisibility is the usual engine: a prime $p$ is forced to divide every variable, and dividing by $p$ gives the smaller solution.

Step 1 — squares are $0$ or $1$ mod $3$, so $x^2 + y^2 \equiv 0 \pmod 3$ forces $x^2 \equiv y^2 \equiv 0$: $3 \mid x$ and $3 \mid y$.

Step 2 — then $9 \mid x^2 + y^2 = 3z^2$, so $3 \mid z^2$ and $3 \mid z$. Hence $\left(\tfrac x3, \tfrac y3, \tfrac z3\right)$ is again a solution.

Step 3 — if a nonzero solution existed, take one with $|x| + |y| + |z| > 0$ minimal; Step 2 gives a nonzero solution with a third of that measure. Contradiction. $\blacksquare$

How to find it. A homogeneous equation is invariant under scaling, so it is enough to find one prime that must divide everything. Try small moduli until one forces all variables to vanish mod $p$.

Step 1 — prove more: for every $k \ge 1$, the only solution of $x^2 + y^2 + z^2 = 2^kxyz$ is $(0, 0, 0)$. The right side is even.

Step 2 — parity cases. All three odd: the left side is odd. Exactly one odd: odd again. Exactly two odd: the left side is $\equiv 2 \pmod 4$, while the right side is $2^k$ times a product containing an even factor, hence divisible by $4$. So all three are even.

Step 3 — writing $x = 2a$, $y = 2b$, $z = 2c$: $4(a^2 + b^2 + c^2) = 2^{k+3}abc$, i.e. $a^2 + b^2 + c^2 = 2^{k+1}abc$ — the same family with $k + 1$. A nonzero solution with minimal $|x| + |y| + |z|$ (over all $k$) would give one with half the measure. So the only solution is $(0, 0, 0)$. $\blacksquare$

How to find it. After halving, the equation is not the same one, so plain descent fails; generalize the constant so that the family is closed under the descent step.

Step 1 — take a solution with $z$ minimal. Then $\gcd(x, y) = 1$ (a common prime $p$ would give the smaller solution $\tfrac xp, \tfrac yp, \tfrac z{p^2}$), so $(x^2, y^2, z)$ is a primitive Pythagorean triple. With $x$ odd, $y$ even, there are coprime $m > n > 0$ of opposite parity with $x^2 = m^2 - n^2$, $y^2 = 2mn$, $z = m^2 + n^2$.

Step 2 — $x^2 + n^2 = m^2$ is again a primitive triple with $x$ odd, so $n$ is even and $x = a^2 - b^2$, $n = 2ab$, $m = a^2 + b^2$ with $\gcd(a, b) = 1$.

Step 3 — then $y^2 = 2mn = 4ab(a^2 + b^2)$, so $ab(a^2 + b^2) = \left(\tfrac y2\right)^2$. The three factors are pairwise coprime ($\gcd(a, b) = 1$ gives $\gcd(a, a^2 + b^2) = \gcd(b, a^2 + b^2) = 1$), and their product is a square, so each is a square: $a = c^2$, $b = d^2$, $a^2 + b^2 = e^2$.

Step 4 — so $c^4 + d^4 = e^2$ is a new positive solution, with $e \le e^2 = m \le m^2 < m^2 + n^2 = z$. This contradicts the minimality of $z$. $\blacksquare$ (Consequently $x^4 + y^4 = w^4$ has no positive solutions: it would give $z = w^2$.)

How to find it. A sum of two squares equal to a square: parametrize the Pythagorean triple. Parametrize again until the pieces are forced to be squares themselves, and the original shape reappears with smaller numbers.