Sign up ×





share|cite|improve this question

15 Answers 15






share|cite|improve this answer
A post on this would be interesting. "all the examples I know are really technical": Don't let this discourage you. – Andrés Caicedo Jul 13 '10 at 14:06

Very simple example:


cannot be proved by induction for obvious reasons, but


is an easy induction problem.


share|cite|improve this answer
I think you mean $\le$ in your statement or else it fails for $n=1.$ – Daniel Parry Sep 6 at 19:01


share|cite|improve this answer
In the base case the LHS=$-\infty$ but the RHS=0. As $n$ increases the LHS is trying to catch up with the RHS. That's why induction fails because the LHS increases more. – Fan Zheng Apr 24 at 22:20

Here's a small example from the book Concrete Mathematics:




share|cite|improve this answer





share|cite|improve this answer





share|cite|improve this answer

Here's a simple example I found in Mathematical Miniatures.





the induction runs smoothly.


share|cite|improve this answer


share|cite|improve this answer
I just read a related question where Sperner's Lemma is also given as an example (but I think it fits better here), see… – j.p. Sep 26 '10 at 16:56

Theorem (difficult): Every planar graph can have its edges directed such that the indegree of each vertex is $\leq 3$.

Strengthening (easy): Every plane graph can have its edges directed such that the indegree of each vertex is $\leq 3$, and the indegree of each vertex on the boundary is $\leq 2$.

Proof: Let $G$ be a plane graph and let the boundary vertices be denoted $x_1, x_2, x_3, \dots, x_n$ in cyclic order. Define the subgraph $H < G$ by deleting $x_2$ and all incident edges. Then we use the induction hypothesis to legitimately direct the edges of $H$, and extend this to $G$ by having $x_2$ have two incoming edges (from $x_1$ and $x_3$) and all other edges be outgoing. The base case is trivial, so the result follows by induction on the order of $G$. QED

Interestingly, when the original problem was set on a selection test for determining the British IMO team, only one person found this elegant proof (which I believe was unknown to the problem-setters, who instead had a meticulous argument involving Euler's formula.

share|cite|improve this answer
@gowers -- This seems compatible with your theory of splitting questions...? – Adam P. Goucher Jun 8 at 12:31
I can't follow why the proof gives that $G$ satisfies the theorem statement, can you explain? For example, it seems like the proof would construct a star graph with all edges pointing to the center, whose in-degree is then too high. – usul Jun 8 at 17:26
Oh, I guess that the proof assumes that all vertices have degree at least 3, but this is okay since you can fully triangulate the graph (and delete the excess edges afterwards). – Adam P. Goucher Jun 8 at 19:48
That makes sense to me, but I'm worried that interior vertices could get too many in-directed edges. If $x_2$ has an edge to a vertex not on the boundary who already has $3$ incoming edges, then we would be adding a fourth incoming edge to that vertex...? – usul Jun 8 at 21:32
Oh, it is a nice proof! General combinatorial fact is the following: if there are at most $d\cdot |U|$ edges joining vertices of any subset $U\subset V(G)$, then $G$ has an orientation with indegrees at most $d$. The condition is necessary for obvious reasons. – Fedor Petrov Sep 6 at 10:38






share|cite|improve this answer



share|cite|improve this answer


share|cite|improve this answer



share|cite|improve this answer

A nice exercise is to prove that the recurrence $T(x+y)\le T(x)+T(y)+\lg(\min\{x,y\})$ is such that $T(n)=O(n)$. (Note that $\lg$ is log base 2.)

The strengthen induction hypothesis is $T(n)\le n-\lg n-1$. Once we have assumed this, we get \begin{eqnarray*} T(x+y) & \le & T(x)+T(y)+\lg(\min\{x,y\})\\ & \le & (x-\lg x-1)+(x-\lg y-1)+\lg(\min\{x,y\})\\ & = & (x+y)-\lg(x+y)-1+(\lg(x+y)+\lg(\min\{x,y\})-\lg x-\lg y-1)\\ & = & (x+y)-\lg(x+y)-1+\lg\frac{(x+y)\min\{x,y\}}{2xy}\\ & \le & (x+y)-\lg(x+y)-1. \end{eqnarray*}

The reason I like example is that it seems that the "-1" is needed.

share|cite|improve this answer

Euler's formula $V-E+F=2$ for convex polytopes has a trivial inductive proof after we replace polytopes to connected planar graphs (remove edges until you get a tree), and even more trivial if we replace 2 to $1+C$, where $C$ is a number of connected components of arbitrary planar graph (remove edges until you get a graph without edges). Note that such operations on a ser of polytopes are not well defined. This is probably a reason why Euler did not prove this fact.

share|cite|improve this answer

Your Answer


