Looking for induction problems that are not formula-based

Question

I am looking for problems that use induction in their proofs such as this one: Given a checker board with one square removed you can cover it with L-shaped pieces made out of three squares. This problem is very different from most induction problems which are algebra driven. Do you know of any other? I am looking for geometrical or algorithmic type problems.

Answer 1

Some problems with some illustrative pictures provided below. All of the problems were taken from Daniel J. Velleman's excelent book How to Prove It: A Structered Approach.

$\textbf{Problem 1:}$ For all $n\in \mathbb{N}$, if $n\ge 3$, then if $n$ distinct points on a circle are connected in consecutive order with straight lines, then the interior angles of the resulting polygon add up to $(n-2)180º$.

Case $n=4$:

Inductive step:

$\textbf{Problem 2:}$ Let $n\in \mathbb{N}$. An equilateral triangle is cut into $4^n$ congruent equilateral triangles, and one corner is removed. Show that the remaining area can be covered by trapezoidal tiles that look like this: .

Case $n=2$:

$\textbf{Problem 3:}$ Let $n\in \mathbb{N}$. Suppose $n$ chords are drawn in a circle in such a way that each chord intersects every other, but no three intersect at one point. Prove that the chords cut the circle into $\displaystyle \frac{n^2+n+2}{2}$ regions.

Case $n=4$:

$\textbf{Problem 4:}$ Let $n\in \mathbb{N}$ and suppose that $n$ chords are drawn in a circle, cutting the circle into a number of regions. Prove that the regions can be colored with two colors in such a way that adjacent regions (that is, regions that share an edge) are different colors.

Case $n=4$:

Answer 2

You might want to look at this pdf: Structure of Proof by Induction, which provides both "traditional, formula based" induction to help explain the logic of inductive proofs, but starts with, and includes some scattered examples of its applicability to recursive-type algorithms and counting arguments: domino problem, coin-change problem.

Indeed, the correctness of the recursive algorithm for solving the Tower of Hanoi Problem boils down to proof by induction (see logical analysis of recursive solution). Inductive proofs are also often used in graph theory.

See also this post linking you to a previous post asking for examples of mathematical induction. You'll get some rich mix of problem types, and see the breadth of its utility!

Answer 3

1. These induction proofs are interesting. Look at examples.

2. Prove that every integer greater than 2 can be written as product of primes.(Strong Induction)

3. Prove than every integer greater than 12 can be made as sum of 4 and 5s.(The original one has to do with coins and postage stamps)