Induction

Claim: $1 + 3 + \cdots + (2n - 1) = n^2$ for all $n \ge 1$. Base: $n = 1$: $1 = 1^2$. Step: assume $1 + 3 + \cdots + (2k - 1) = k^2$ for some $k \ge 1$. Adding the next odd number, $1 + \cdots + (2k - 1) + (2k + 1) = k^2 + 2k + 1 = (k + 1)^2$, which is the claim for $k + 1$. $\blacksquare$

Claim: $7 \mid 8^n - 1$ for all $n \ge 0$. Base: $8^0 - 1 = 0 = 7\cdot0$. Step: assume $7 \mid 8^k - 1$. Then $8^{k+1} - 1 = 8\cdot8^k - 1 = 8(8^k - 1) + 7$. The first term is divisible by $7$ by the hypothesis and the second is $7$, so $7$ divides the whole. $\blacksquare$

Claim: $2^n > n^2$ for all $n \ge 5$. Base: $2^5 = 32 > 25$. Step: assume $2^k > k^2$ for some $k \ge 5$. Then $2^{k+1} = 2\cdot2^k > 2k^2 = k^2 + k^2 \ge k^2 + 5k > k^2 + 2k + 1 = (k + 1)^2$. $\blacksquare$

Assume every $j$ with $2 \le j \le k$ is a product of primes. If $k + 1$ is prime, it is a product of one prime. Otherwise $k + 1 = ab$ with $2 \le a, b \le k$; each is a product of primes by hypothesis, and so is their product. $\blacksquare$ (Ordinary induction fails here: the factors of $k + 1$ are not $k$.)

Every $n \ge 12$ is a sum of $4$s and $5$s. Bases: $12 = 4+4+4$, $13 = 4+4+5$, $14 = 4+5+5$, $15 = 5+5+5$. Step: for $k + 1 \ge 16$, $(k + 1) - 4 \ge 12$ is a sum of $4$s and $5$s by hypothesis; add a $4$. $\blacksquare$ (Four base cases because the step reaches back $4$.)

"Claim": $n^2 + n + 1$ is even for every $n \ge 1$. The step is genuinely valid: $(k + 1)^2 + (k + 1) + 1 = (k^2 + k + 1) + 2(k + 1)$, so if $k^2 + k + 1$ is even, so is the next value. But the base fails: $n = 1$ gives $3$. In fact $n^2 + n + 1 = n(n + 1) + 1$ is always odd. Flaw: no base case — the chain was never started.

"Claim": in any group of $n \ge 1$ horses, all have the same color. Base: one horse matches itself. Step: in a group of $k + 1$, the first $k$ share a color and the last $k$ share a color; the horses in both groups link the two, so all $k + 1$ match. Flaw: the step needs the two groups to overlap, and for $k = 1$ (a group of two) the "first one" and "last one" are different horses with nothing in common. The step fails at exactly one link, from $1$ to $2$, and that is enough to break the whole chain.

Claim: a set with $n$ elements has $2^n$ subsets. Base: the empty set has exactly one subset, itself, and $2^0 = 1$. Step: take any set with $k + 1$ elements and pick one element $x$. Subsets not containing $x$ are the subsets of the other $k$ elements: $2^k$ by hypothesis. Subsets containing $x$ are those same $2^k$ sets with $x$ added. Total $2^k + 2^k = 2^{k+1}$. $\blacksquare$

Claim: for every $n \ge 1$, a $2^n \times 2^n$ board with any one square removed can be tiled by L-shaped pieces of three squares. Base $n = 1$: a $2 \times 2$ board minus one square IS an L. Step: cut a $2^{k+1} \times 2^{k+1}$ board with one square missing into four $2^k \times 2^k$ quadrants. The missing square is in one quadrant. Place one L at the centre so that it covers the corner square nearest the centre in each of the other three quadrants. Now every quadrant is a $2^k \times 2^k$ board with one square missing, and the hypothesis tiles each. $\blacksquare$