# Mathematical induction without simplifying equations or inequalities

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.

• Here is another example, prove that for any $n ≥ 1$ a $2ⁿ × 2 ⁿ$ checkerboard with $1 × 1$ corner square removed can be tilted using L tromionoes, because here too we don't need simplifications of equations or inequalities. Mar 20, 2023 at 1:54
• Similar question on Math SE Mar 20, 2023 at 8:29

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).

• IME teaching discrete mathematics, these examples all seem very advanced -- usually things the instructor would have to guide students through, and each taking several dense pages in the textbook. Which seems at odds with what the OP is requesting. Mar 19, 2023 at 18:20
• The planar polygon example could be taught to anyone (especially with an additional hypothesis of convexity). Mar 19, 2023 at 18:37
• @DanielR.Collins, maybe they're harder than they look, but a few look doable for this level of student: the triangulation and Hanoi sound interesting. Mar 19, 2023 at 18:37
• @SueVanHattum: In Rosen, triangulation is 3 pages (16 dense paragraphs, Sec. 5.2). Hanoi is 2 pages (9 paragraphs, Sec. 8.1). Mar 20, 2023 at 0:56
• @SueVanHattum: The details all look necessary to my eye. Mar 20, 2023 at 6:21

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).

• Thank you very much for sharing much important relevant information . Mar 19, 2023 at 18:28