Classical examples of mathematical induction
What are some interesting, standard, classical or surprising proofs using induction?
Here is what I got so far:
- There are some very standard sums, e.g, $\sum_{k=1}^n k^2$, $\sum_{k=1}^n (2k-1)$ and so on.
- Fibonacci properties (there are several classical ones).
- The Tower of Hanoi puzzle can be solved in $2^n-1$ steps.
- A $2^n \times 2^n$-grid with one square missing can be covered with $L$-triominos.
- Cayley's formula for labeled forests.
- Every square can be subdivided into any number $n\geq 6$ subsquares.
- The Art gallery problem.
- Number of regions determined by $n$ lines in general position.
- Eulers formula $V-E+R=2$.
- Planar graphs are 5-colourable.
- Properties about binomial coefficients (I do not count these as classical, since the proofs are very mundane and not really fun - IMHO, such identities should be proved by a bijective argument / combinatorial interpretetation).
In other words, what would you expect to see in a book titled "Induction in Mathematics", aimed for freshmen/undergraduate students?
I really like the tilings with $L$-triominos problem - it is easy to state, has a neat proof that requires some creativity.
Neat examples from calculus and probability would be appreciated.
If you want to break the chocolate bar below into its $28$ individual pieces, then what is the minimum number of breaks to do this with? You can only break one chunk of chocolate into two pieces at a time.
The answer is that it takes of course exactly $27$ breaks, no matter how you do it. This is often surprising to people, as many think that maybe breaking the chunk into somewhat 'equal chunks', or breaking any chunk along the longest break line would somehow end up doing things faster. However, a quick and simple proof by (strong) induction shows that it has to be $n-1$ breaks for $n$ pieces.
Also, you can continue this problem with: Take the same chocolate bar as above, and once again you want to break it into its $28$ individual pieces. This time, however, you can score points every time you make a break: If you break a chunk of chocolate of size $n$ into two pieces of size $k$ and $n-k$, then you receive $k \cdot (n-k)$ points. Now: what is the maximum number of points you can get?
And again, you can prove by strong induction that no matter how you break up the bar, your total score in the end will be $\frac{n(n-1)}{2}$. Here is a proof by picture, knowing that $\frac{n(n-1)}{2}$ is the sum of all numbers $1$ through $n-1$ (i.e. triangular number $T_{n-1}$):
This picture shows that $T_{n-1}=k(n-k)+T_{k-1}+T_{n-k-1}$, so using the inductive hypothesis that the score you get for breaking apart a chunk of chocolate of size smaller than $n$ always gives you a score of $T_{k-1}$, no matter how you break it up, we obtain that the score of breaking the chunk with $n$ pieces gives you $k(n-k)+T_{k-1}+T_{n-k-1}=T_{n-1}$ points, no matter where you place the next break.
A book 'aimed for freshmen' should not miss the All horses are the same color example of a simple flaw possible in an inductive reasoning.
Every integer greater than $1$ is either prime or a product of primes. (Strong Induction)
Euler Path Theorem (it is also called as "Euler Theorem" but Euler Path Theorem includes both the existence of Euler Path and Euler Circuit). A connected graph has an Euler circuit if and only if it has no vertex with odd degree. It can be proven with strong induction as explained in here: http://mathonline.wikidot.com/euler-s-theorem