Mathematical induction without simplifying equations or inequalities

Question

We discuss lot of questions related to mathematical expressions consisting equations or inequalities in mathematical induction. What are the examples where we can apply mathematical induction as the method of proof in proving statements without involving equation or inequality for advanced level students. I think this kind of problems may be quite interesting to improve creative skills in mathematics.
Here is one example to get the clear picture of the issue
Finitely many lines divide a plane into regions. Show that these regions can be coloured by two colours in such a way that neighboring regions have different colours.

Answer 1

Here are a few examples (for students at very different levels, since it's rather subjective what constitutes an "advanced level"):

• The task in the Towers of Hanoi puzzle is solvable. (The Towers of Hanoi are often used as an example for a recursive algorithm - but one can, of course, also frame it as an example for induction.)

• A classic: existence of the prime factorization of integers.

• A compact metric space (or, more generally, a compact topological Hausdorff space) which is countable and infinite contains infinitely many isolated points.

• Identity theorem for polynomials: if a complex polynomial of degree $d \ge 0$ vanishes at $d+1$ distinct points, then it is $0$ (can be shown by induction over $d$, splitting off a linear factor in the inductive step).

  (One might argue that there is certainly a small computational part in the induction step - but I'd argue that the overall argument is theoretical rather than computional in nature, so it's not one of typical "Show the following equality by writing down a chain of identities in the induction step" problems.)

• Every planar polygon with $n$ vertices can be written as the union of $n-2$ triangles.

  (For non-convex polygons this contains a subtlety, though: one first needs to show that every polygon can be split into two polygons by connecting to appropriately chosen vertices.)

• Here's a weird one (I'd only recommend it for students who are up to dealing with technical subtleties):

  For a set $X$ and an associative binary operation $\circ: X \times X \to X$, composing finitely many elements $x_1, \dots, x_n$ (in this order) by any use of parantheses yields the same result.

  Note that, for this exercise to make sense, one a priori needs to define an $n$-ary operation $X^n \to X$ by fixing an order of evaluation, e.g. $x_1 \circ \dots \circ x_n := \Big( \dots (x_1 \circ x_2) \circ \dots x_n \Big)$.

  (The claimed property seems intuitively clear and in each algebra course I have ever participated in, as a student or teacher, we just glossed over this without really doing the induction - and, as I said above, I would only recommend to discuss it in detail if one has very strong students).

Answer 2

The textbook I use for Discrete Mathematics has some lovely inductive proof problems. (And it's OER.) Discrete Mathematics: An Open Introduction, by Oscar Levin.

I especially like the stamps problem he uses to introduce the topic (section 2.5), and the number of squares problem (in the exercises, #29).