Good, simple examples of induction? - Mathematics Educators Stack Exchange most recent 30 from matheducators.stackexchange.com 2019-09-16T00:57:10Z https://matheducators.stackexchange.com/feeds/question/220 https://creativecommons.org/licenses/by-sa/4.0/rdf https://matheducators.stackexchange.com/q/220 34 Good, simple examples of induction? vonbrand https://matheducators.stackexchange.com/users/123 2014-03-15T20:08:16Z 2019-07-08T00:08:48Z <p>Many examples of induction are silly, in that there are more natural methods available. Could you please post examples of induction, where it is required, and which are simple enough as examples in a course on proofs (or which includes proofs, e.g. a first course on discrete mathematics)?</p> https://matheducators.stackexchange.com/questions/220/-/233#233 18 Answer by Brendan W. Sullivan for Good, simple examples of induction? Brendan W. Sullivan https://matheducators.stackexchange.com/users/80 2014-03-15T21:57:08Z 2014-03-15T21:57:08Z <ul> <li>Proving DeMorgan's Laws for $n$ sets. I like this example because it requires the $n=2$ case in the induction step.</li> <li>It's common to have students prove that $\sum_{k=1}^n k^3 = \left(\sum_{k=1}^n k\right)^2$. A great follow up is to assume you have a sequence $\langle a_k\rangle$ that satisfies $\sum_{k=1}^n a_k^3 = \left(\sum_{k=1}^n a_k\right)^2$ and prove, by induction on $n$, that necessarily $a_k=k$ for all $k$.</li> <li>Proving the Well-Ordering Principle of $\mathbb{N}$ by induction on whether the set in question has $n$ as an element. I designed a scaffolded version of this as a homework exercise, and it also has the students think about why induction on the <em>size</em> of the set in question does not prove the claim!</li> <li>Have not personally used this, but perhaps <a href="http://www.proofwiki.org/wiki/Cauchy%27s_Mean_Theorem">Cauchy's "backward induction" proof</a> of the AGM inequality is of interest.</li> </ul> https://matheducators.stackexchange.com/questions/220/-/237#237 11 Answer by Ittay Weiss for Good, simple examples of induction? Ittay Weiss https://matheducators.stackexchange.com/users/59 2014-03-15T22:49:18Z 2014-03-15T22:49:18Z <p>Induction receives far too much attention as a proof technique. But, if you are to give it attention, it is probably worth-while going through the equivalence of the principle of induction and the well-ordering of the naturals. In fact, when I teach induction I proceed as follows: Suppose an inductive property does not hold for all naturals. Look at the set of counter-examples, and pick the smallest one. Arrive at a contradiction and conclude the property did hold for all naturals. I find that this approach is very natural (pun not intended). The equivalent formalism of prove case $k=1$, then prove $P(k)\implies P(k+1)$ is something I only introduce later. For the life of me I don't understand why this formalism is the standard one and not the "look at all counter-example....". </p> <p>It is probably also a good idea to talk about the status of the principle of induction. It is not a theorem but rather a proof principle. It is ok not to accept it (though most mathematicians do). It is important to understand that what we accept by proof by induction is that a single recipe for proofs (i.e., for each $k$ we have a recipe for how to concoct a proof for $P(k)$) is accepted as a single proof for an infinitude of statement (i.e., all the $P(k)$ for all natural $k$). It is a good idea to talk about this in relation to the demand that proofs are finite. It is also a good idea to explain this in the context of the axiom of choice.</p> <p>It is indeed quite hard to find good examples of proof by induction (which is part of the reason why I claimed that induction receives far too much attention). Other than the classical (more or less silly) exercises, some that actually do require induction include: the generalized associativity rule and other generalized algebraic rules but also proving properties of recursively defined sequences (e.g., monotonicity, boundedness etc.). </p> https://matheducators.stackexchange.com/questions/220/-/242#242 17 Answer by Daryl for Good, simple examples of induction? Daryl https://matheducators.stackexchange.com/users/71 2014-03-16T00:55:03Z 2014-03-16T00:55:03Z <p>One example that I recently came across was to prove that the function $$f(x)=\begin{cases} e^{-1/x},&amp;x&gt;0\\ 0,&amp;x\leq0 \end{cases}$$ is smooth (i.e. $f\in\mathcal{C}^\infty$). <a href="http://andromeda.rutgers.edu/~loftin/difffal03/bump.pdf">Here</a> a link to a proof online.</p> https://matheducators.stackexchange.com/questions/220/-/273#273 7 Answer by dtldarek for Good, simple examples of induction? dtldarek https://matheducators.stackexchange.com/users/42 2014-03-16T16:33:21Z 2014-03-16T22:38:54Z <p><strong>Disclaimer:</strong></p> <p>It's not simple, but it might be useful. The context in which it happend is algorithms, but it would be great if someone could test if this approach is useful during other courses, e.g. when introducing induction. Reason why I'm writing about this here is, that when I did the exercise described below, my students (not all, but a lot) had this "being enlightened" face expression, and as it was not about the algorithm itself, then it had to be about the other thing and in that case it was induction (i.e. it seemed that they grasped something important about induction).</p> <p><strong>Exercise:</strong></p> <p>The task was on dynamic programming and was given as follows:</p> <blockquote> <p>A company plans to organize a party. The hierarchy of employees is a rooted tree (not necessarily binary), and each employee can be characterized by a form of sociability, given by a positive number. Write a program that will pick the guests so that:</p> <ul> <li>no guest would meet their immediate superior at the party,</li> <li>the sum of sociability coefficients is maximal,</li> <li>the company founder (the root of the tree) has to be at the party.</li> </ul> <p>The program should output a single number, namely the sum of sociability coefficients of the guests.</p> </blockquote> <p>The algorithm to calculate it is easy, let the symbol $\mathcal{T}$ denote the set of abstract people with their hierarchies</p> <p>\begin{align*} \newcommand{soc}{\mathtt{sociability}} \newcommand{sub}{\mathtt{subordinates}} \newcommand{with}{\mathtt{with}} \newcommand{without}{\mathtt{without}} \soc &amp;: \mathcal{T} \to \mathbb{R}^+\\ \sub &amp;: \mathcal{T} \to 2^\mathcal{T} \\ \end{align*} then in mathematical notation it would be \begin{align*} \with(t)&amp;= \soc(t) + \sum_{s\ \in\ \sub(t)} \without(s), \\ \without(t) &amp;= \sum_{s\ \in\ \sub(t)} \max\big\{ \with(s), \without(s) \big\}. \end{align*}</p> <p>where the result will be given by $\with$ as the founder has to be included. Now, the challenge is to prove that it is optimal (i.e. it returns the correct result). The proof is via induction on the structure of the tree, that is, we start from leaves and then go up to the root, with the assumption that each time when make the step in some node, all its subtrees are already done.</p> <p>The base step is easy, as for each leaf we have $\sub(l) = \varnothing$ so \begin{align}\with(l) &amp;= \soc(l) \\ \without(l) &amp;= 0 \end{align} what is obviously true.</p> <p>Now, for the induction step, $\with(t)$ requires all the subtrees to skip their roots, and besides that they are all independent, so we can just take the sociability of $t$ and add all the optimal subsolutions (we can use them because of the induction hypothesis) and that is exactly what the formula is doing. As for $\without(t)$ the $t$ itself isn't a guest, so from each subtree we can pick the best option and sum it all together. This works, but only because we know that the subsolutions were calculated correctly from induction hypothesis, the shape of the tree ensures, that there weren't any circular arguments.</p> <p>Sometimes students benefit from an alternative proof: take an optimal solution and prove that one returned by the algorithm isn't worse. Again, prove it via induction on the structure of the tree, the hypothesis being that our algorithm returns an optimal subsolution for each node of the tree. Base case is easy, because there is no choice available in the leaves. For the inner nodes we show that our algorithm returns a pick of guests at least as good as the optimal solution (in $\with$ it follows from induction hypothesis and the fact that all the numbers are positive, for $\without$ it follows from properties of $\max$ function).</p> <p><strong>Some commentary:</strong></p> <p>Each time I did this it was an introductory course in programming, and for many the first time where they would see a non-linear induction (in fact this <em>can</em> be proved with induction on the height of the tree, but I did complicate it on purpose). Drawing a diagram with arrows, describing how the induction progresses and how it relies on the subtrees being already calculated helps a lot. After this exercise the topic would come back again several times and students would have much easier time proving that some algorithm (e.g. the Ackermann function) terminates. </p> <p>Of course, it is hard to draw any reliable conclusions from this experience (it might be just a coincidence that it worked for me), so it would be great if someone could test it themselves. I'd also love to hear your opinions and suggestions.</p> <p>I hope this helps $\ddot\smile$</p> https://matheducators.stackexchange.com/questions/220/-/304#304 23 Answer by Santiago Canez for Good, simple examples of induction? Santiago Canez https://matheducators.stackexchange.com/users/18 2014-03-16T22:50:30Z 2014-05-20T23:11:03Z <p>Two more examples.</p> <ol> <li><p>Proving that a $2^n \times 2^n$ chessboard with a single square missing can be covered using L-shaped (made out of three squares) pieces.</p></li> <li><p>Proving that a convex $n$-gon can be divided into $n-2$ triangles.</p></li> </ol> https://matheducators.stackexchange.com/questions/220/-/305#305 12 Answer by Jill-Jênn Vie for Good, simple examples of induction? Jill-Jênn Vie https://matheducators.stackexchange.com/users/171 2014-03-16T23:08:13Z 2019-07-08T00:08:48Z <p>I indeed think <span class="math-container">$\sum_{k = 1}^n k = \frac{n(n + 1)}2$</span> is not a good first example as writing the sum forwards and backwards is more clever and natural for a newcomer.</p> <p>But proving “the sum of the <span class="math-container">$n$</span> first odd numbers is <span class="math-container">$n^2$</span>”, while really close to the equality above, is a better example, because the induction part of the proof is really simple: <span class="math-container">$\sum_{k = 1}^{n + 1}(2k-1)= \left(\sum_{k = 1}^n(2k-1)\right) + 2n + 1 = n^2 + 2n + 1 = (n + 1)^2$</span>.</p> <p>Proof by induction is more necessary and useful in a computer science scenario, where some objects are defined in an inductive way: “a complete binary tree of height <span class="math-container">$n$</span> has <span class="math-container">$2^n - 1$</span> nodes”: straightforward for <span class="math-container">$n = 1$</span>; for <span class="math-container">$n \geqslant 2$</span>, its left and right child are binary trees of height <span class="math-container">$n - 1$</span>, so it has <span class="math-container">$2(2^{n - 1} - 1) + 1 = 2^n - 1$</span> nodes.</p> <p>Another example where a special method of inductive reasoning called <em><a href="https://en.wikipedia.org/wiki/Infinite_descent" rel="nofollow noreferrer">infinite descent</a></em> is useful: “show that <span class="math-container">$\sqrt2$</span> is irrational”. Let us assume there exist two natural numbers <span class="math-container">$p, q$</span> such that <span class="math-container">$\sqrt2 = p/q$</span>. Then <span class="math-container">$2q^2 = p^2$</span>, so <span class="math-container">$p$</span> is even, thus there exists some natural number <span class="math-container">$p'$</span> such that <span class="math-container">$p = 2p'$</span>, therefore <span class="math-container">$2q^2 = 4p'^2$</span> gives <span class="math-container">$q^2 = 2p'^2$</span> so <span class="math-container">$q$</span> is even as well, <em>i.e.</em> <span class="math-container">$q = 2q'$</span> holds for some natural number <span class="math-container">$q'$</span>. We then get <span class="math-container">$2q'^2 = p'^2$</span>, so <span class="math-container">$(p', q') = (p / 2, q / 2)$</span> is a strictly lesser representation of <span class="math-container">$\sqrt2$</span>. As there is no infinite decreasing sequence of natural numbers, this leads to a contradiction, so <span class="math-container">$\sqrt2$</span> is irrational.</p> https://matheducators.stackexchange.com/questions/220/-/1255#1255 18 Answer by Benjamin Dickman for Good, simple examples of induction? Benjamin Dickman https://matheducators.stackexchange.com/users/262 2014-04-03T01:18:23Z 2014-04-03T01:18:23Z <p><strong>Historical remark.</strong> Though it has already been mentioned in an answer, I can't resist posting a bit more about the following wonderful example of a proof by induction. </p> <p>I quote directly from the original printing of <em>Polyominoes</em> (1965) by Solomon Golomb:</p> <blockquote> <p><em>T R O M I N O E S</em></p> <p>It is impossible to cover an $8 \times 8$ board entirely with <em>trominoes</em>, polyominoes of $3$ squares, because $64$ is not divisible by $3$. Instead, it shall be asked: Can the $8 \times 8$ board be covered with $21$ trominoes and $1$ <em>monomino</em> (a single square)? (p. 20).</p> </blockquote> <p>In this particular problem, Golomb is talking about trominoes that look like extended dominoes. He demonstrates that this is only possible when the monomino is placed in one of four different squares, and then begins his discussion of L-shaped trominoes:</p> <blockquote> <p>When another type of tromino is considered, the result is surprisingly different: No matter where on the checkerboard a monomino is placed, the remaining squares always can be covered with $21$ right trominoes [i.e., L-shaped trominoes] (p. 21).</p> </blockquote> <p>He then proceeds to prove this for the $8 \times 8$ board, but also for the $2^n \times 2^n$ board, remarking:</p> <blockquote> <p>The proof just given proceeds by <em>mathematical induction</em>... (p. 22).</p> </blockquote> <p>As a spoiler, here is a proof:</p> <p><img src="https://i.stack.imgur.com/JfhAV.jpg" alt="enter image description here"></p> <p>The pasted image above comes from a nice article based on earlier work by Norton Starr:</p> <blockquote> <p>Soifer, A. (2010). Norton Starr’s 3-Dimensional Tromino Tiling. <em>Geometric Etudes in Combinatorial Mathematics</em>, 221-225. Springer New York.</p> </blockquote> <p>You can find further information about this problem on Starr's site <a href="http://www3.amherst.edu/~nstarr/trom/intro.html" rel="noreferrer">here</a>. In particular, you can find a list of related references as well as a gamefied version of the problem that can be played online (or purchased as an actual puzzle - a nice gift!).</p> <p>Though the latter tromino problem is solved using induction, the former one is also quite nice. The first to formulate that problem was, apparently, prolific problem poser <a href="http://en.wikipedia.org/wiki/Murray_S._Klamkin" rel="noreferrer">Murray S. Klamkin</a>:</p> <blockquote> <p>...back in $1948$ ... I had begun to submit a rather large number of problem proposals to the American Mathematical Monthly. ...Since probably at that that time, in retrospect, most of my proposals were not particularly good, they just got filed away. Unfortunately for me, this included one favorite one. This was to determine whether or not one could remove one square from a chess board and cover the deleted board with $21$ $3 \times 1$ trominoes. This was no loss to problem solvers, since several years later, Solomon Golomb's book on polyominoes came out which included this problem plus many more goodies (p. 73).</p> </blockquote> <p>This remark comes from (<strong>N.B.</strong> Good luck tracking down part one of this article...):</p> <blockquote> <p>Klamkin, M. S. (1994). Mathematical Creativity in Problem Solving and Problem Proposing II. <em>In Eves' circles</em>, (34), 73-95.</p> </blockquote> <p>Sorry if the tangent here seems unrelated; problem histories can be surprisingly tough to figure out, so I thought it might be nice to include a bit of the back-story online.</p> https://matheducators.stackexchange.com/questions/220/-/1258#1258 24 Answer by Bernard Masse for Good, simple examples of induction? Bernard Masse https://matheducators.stackexchange.com/users/503 2014-04-03T03:36:39Z 2016-03-06T20:00:02Z <p>The problem with induction proofs is that too often the problem is given by "Prove that..."</p> <p>After a few examples and explanations of induction, if the students know elementary calculus, the following sequence might prove interesting:</p> <blockquote> <ol> <li>Find the first ten derivatives of $x\cdot e^x$.</li> <li>What seems to be the formula for the $n$th derivative of $x\cdot e^x$?</li> <li>Prove that your formula is right by induction.</li> <li>Find and prove a formula for the $n$th derivative of $x^2\cdot e^x$. When looking for the formula, organize your answers in a way that will help you; you may want to drop the $e^x$ and look at the coefficients of $x^2$ together and do the same for $x$ and the constant term.</li> </ol> </blockquote> <p>I'd have the students work this out in class and in teams of two and their work was corrected and counted as a homework. Of course, the use of a CAS helped getting rid of the messy part of finding derivatives. Not all students found this interesting. But those who did started to learn what it was to do (elementary) research.</p> https://matheducators.stackexchange.com/questions/220/-/1276#1276 7 Answer by Benoît Kloeckner for Good, simple examples of induction? Benoît Kloeckner https://matheducators.stackexchange.com/users/187 2014-04-03T19:12:36Z 2016-03-08T16:56:38Z <p>I suggest the following counter-example. (<strong>Added in edit:</strong> I agree with kcrisman comment that this may be misleading to beginners, and should probably be kept for people that master induction relatively well and start being lazy verifying the base case).</p> <blockquote> <p><strong>Theorem.</strong> In a (finite) color pencils box, all pencils must have the same color.</p> <p><em>Proof.</em> We proceed by induction on the number of pencils. If the box has one pencil, then obviously all its pencils have the same color. Now, assume that in all boxes of $n$ pencils, the pencils are all of the same color and let $X$ be a box with $n+1$ pencils. Order the pencils arbitrarily and consider the $n$ first pencils: by the induction hypothesis, they all have the same color, call it $c$. Consider now the $n$ last pencils: by the induction hypothesis, they all have the same color, call it $c'$. Since the $n-1$ central pencils have color $c$ and $c'$, we have $c=c'$ so that all $n+1$ pencils have the same color.</p> </blockquote> <p>The goal here is to stress that if one fails to properly identify and test the base case, then things can go dead wrong.</p> https://matheducators.stackexchange.com/questions/220/-/1894#1894 1 Answer by Colin Tan for Good, simple examples of induction? Colin Tan https://matheducators.stackexchange.com/users/1178 2014-04-22T16:47:59Z 2014-04-22T16:47:59Z <p>Every natural number is odd or even.</p> https://matheducators.stackexchange.com/questions/220/-/1910#1910 10 Answer by Ross Sweet for Good, simple examples of induction? Ross Sweet https://matheducators.stackexchange.com/users/651 2014-04-22T22:09:25Z 2014-04-22T22:09:25Z <p>I like having students show that the Euler characteristic ($\chi=V-E+F$, where $V$, $E$, and $F$ are the number of vertices, edges, and faces, including the exterior face, of the graph) of a planar graph is always 2. Planar graphs are easy to define for those who have not seen them before, and the proof is a (relatively) straightforward induction on the number of edges in a graph.</p> <p>Further, after giving the definition of a planar graph, there is ample opportunity for students to explore and come up with a conjecture on their own (assuming you have the time for this). This seems a much more natural way to show how induction is used by mathematicians, rather than just stating "Prove that...".</p> <p>Another benefit is giving a concrete example of a topological invariant, likely the first seen by your students. Finally, it's not too difficult to motivate why non-math majors should care about graphs. There are dozens and dozens of applications (e.g. neural networks). It is likely that whatever the major of the student, there is some problems in that field for which graphs are useful tools.</p> https://matheducators.stackexchange.com/questions/220/-/1913#1913 4 Answer by Robert Talbert for Good, simple examples of induction? Robert Talbert https://matheducators.stackexchange.com/users/942 2014-04-23T00:32:07Z 2014-04-23T00:32:07Z <p>Computational geometry is a good source for basic induction proofs where non-inductive methods are either impossible or hard to conceive. </p> <p>Also graph theory. Someone already mentioned Euler's Formula which is great. It's also simple to prove that every connected simple graph can be 6-colored using induction. (You can assume in such a graph that there exists a vertex whose degree is less than or equal to 5 -- or prove it separately.) </p> <p>For a CS-oriented audience, proofs of correctness for recursive algorithms are a great way to motivate induction -- especially because induction and recursion go hand in hand. Here's a nice video proof from Udacity on the correctness of the Russian peasant's algorithm for integer multiplication: <a href="https://www.youtube.com/watch?v=GGBEiIuheTY" rel="nofollow">https://www.youtube.com/watch?v=GGBEiIuheTY</a></p> https://matheducators.stackexchange.com/questions/220/-/2430#2430 9 Answer by Frank Thorne for Good, simple examples of induction? Frank Thorne https://matheducators.stackexchange.com/users/1535 2014-05-26T00:05:02Z 2014-05-26T00:05:02Z <p>Prove that the <a href="http://en.wikipedia.org/wiki/Tower_of_hanoi" rel="noreferrer">Tower of Hanoi</a> puzzle can be solved for any number of disks. Indeed, that it can be solved in $2^n - 1$ moves for $n$ disks.</p> https://matheducators.stackexchange.com/questions/220/-/2446#2446 3 Answer by user21820 for Good, simple examples of induction? user21820 https://matheducators.stackexchange.com/users/1550 2014-05-27T14:26:33Z 2014-05-27T14:26:33Z <p>Prove that the <a href="http://en.wikipedia.org/wiki/Change-making_problem#Greedy_method" rel="nofollow">greedy algorithm for the change-making problem</a> with Fibonacci denominations produces an optimal solution (uses the minimum number of coins possible).</p> <p>This problem is not as easy as it looks. Note that there may be more than one optimal solution. It would also be instructive to try and minimize the number of times the induction axiom is used. (But no, I won't suggest that one should also try to <em>prove</em> this minimum. =P)</p> https://matheducators.stackexchange.com/questions/220/-/2449#2449 9 Answer by user21820 for Good, simple examples of induction? user21820 https://matheducators.stackexchange.com/users/1550 2014-05-27T17:02:42Z 2014-05-27T17:02:42Z <p><strong>Base problem</strong></p> <p>Some positive integers are written on the board. At each step one of the integers $n$ is erased and replaced with any number of positive integers that are all less than $n$. Of course, if the erased integer is $1$ then no new positive integers can be written on the board. Prove that no matter how this procedure is carried out the board must eventually become empty.</p> <p>This problem is just the right difficulty and can ensure that students really understand what induction is.</p> <p><strong>General problem</strong></p> <p>Prove that the following game always terminates regardless of the initial configuration and the choices (of node, subtree and number of copies) throughout the game.</p> <p>(1) Start with any finite tree rooted at $r$</p> <p>(2) At each step:</p> <p>&emsp; (2.1) Select any node $x$ and a child node $y$ of $x$</p> <p>&emsp; (2.2) Remove the subtree rooted at $y$ (and of course the edge $(x,y)$ as well)</p> <p>&emsp; (2.3) If $x$ is not $r$, attach finitely many copies of the subtree rooted at $x$ to its parent node</p> <p>For example, the following diagram shows one step, where the chosen subtree to be removed is shown in red and the subtree that would be copied is shown in green.</p> <p><img src="https://i.stack.imgur.com/qjaak.png" alt=""></p> <p>The base problem is equivalent to the special case of this general problem where the initial tree has depth at most $2$. This generalization is a harder problem that is an extension of the <a href="http://en.wikipedia.org/wiki/Hydra_game" rel="noreferrer">Hydra Game</a>. A hint is to define a total ordering on trees:</p> <p>For any finite trees $S,T$:</p> <p>&emsp; $S \le T$ iff:</p> <p>&emsp; &emsp; Either:</p> <p>&emsp; &emsp; &emsp; $S$ is a leaf node</p> <p>&emsp; &emsp; Or:</p> <p>&emsp; &emsp; &emsp; $S,T$ are both not leaf nodes</p> <p>&emsp; &emsp; &emsp; The subtrees of $S$ when ordered forms a lexicographically smaller sequence than that of $T$</p> <p>Then one must show that at each step the whole tree decreases according to the ordering, and also that any decreasing sequence of trees must terminate. That last part is the hardest. Basically, induct on the tree depth first, which then allows inducting on the biggest subtree, and then induct on the number of copies of the biggest subtree.</p> <p>Note that this proof shows that with the right definitions and inductions it is quite intuitive, and there is no need to introduce ordinals.</p> https://matheducators.stackexchange.com/questions/220/-/2454#2454 5 Answer by Joseph O'Rourke for Good, simple examples of induction? Joseph O'Rourke https://matheducators.stackexchange.com/users/511 2014-05-27T23:49:25Z 2014-05-27T23:49:25Z <p>Three connected induction proofs:</p> <p>(1) For a really easy one: Every tree of $n$ arcs has $n+1$ nodes. ($0$ arcs $\implies$ $1$ node. Remove a leaf node and its incident arc; induct.)</p> <p>(2) A bit more difficult: Every polygon triangulation can be $3$-colored. Assume every polygon has a triangulation. See below. Argue that the dual graph is a tree. Remove a leaf node by clipping off an "ear tip." $3$-color the remainder and return the ear triangle, coloring its tip different from its two neighbors. <hr /> &nbsp; &nbsp; &nbsp; <img src="https://i.stack.imgur.com/DbNcf.png" alt="3-coloring"></p> <hr /> <p>(3) Every polygon has a triangulation. Prove there exists an interior diagonal. Induct on the two halves. Proved, e.g., in <a href="http://cs.smith.edu/~orourke/DCG/" rel="noreferrer"><em>Discrete and Computational Geometry</em></a>, p.4.</p> https://matheducators.stackexchange.com/questions/220/-/10726#10726 1 Answer by kcrisman for Good, simple examples of induction? kcrisman https://matheducators.stackexchange.com/users/1608 2016-03-08T15:33:19Z 2016-03-08T15:33:19Z <p>Although building up to it might be beyond the time available in many courses introducing induction, an interesting elementary example that seems unbelievable but is very easy to verify in any given case is <a href="http://mathforum.org/library/drmath/view/65670.html" rel="nofollow">Pick's Theorem</a>. </p>