What is wrong with the following proof that “all rulers have the same length" using induction?
Base case: suppose that we have one ruler, then clearly it clearly has the same length as itself.
Assume that any \(n\) rulers have the same length for the induction hypothesis. If we have \(n+1\) rulers, the first \(n\) ruler have the same length by the induction hypothesis, and the last \(n\) rulers have the same length also by induction hypothesis. The last ruler has the same length as the middle \(n-1\) rulers, so it also has the same length as the first ruler. This means all \(n+1\) rulers have the same length.
By the principle of mathematical induction, all rulers have the same length.
Given a series of statements enumerated by the natural numbers, the strong induction principle says the following. Suppose that
The 1st statement is true (the base case).
Whenever all statements up to and including the \(n\)th statement is true, the \((n+1)\)th statement is also true (induction step).
Then the statement is true for all natural numbers. Show that the strong induction principle works.
Prove that each natural number \(n\geq 2\) can be uniquely written as a product of prime factors. More precisely, there are prime numbers \(p_1,\dots,p_s\) such that \(n = p_1\dots p_s\). Moreover, if \(n = q_1\dots q_l\) where \(q_1,\dots,q_l\) are prime, then \(s=l\) and after reordering we have \(q_1 = p_1,\dots,q_s=p_s\). This is the fundamental theorem of arithmetic.
The AM-GM inequality asserts that the arithmetic mean of nonnegative numbers is always at least their geometric mean. That is, if \(a_1,\dots,a_n\geq 0\), then \[\frac{a_1+\dots+a_n}{n}\geq \sqrt[n]{a_1\dots a_n}.\] Prove this inequality.
There are many proofs of this fact and quite a few of them are by induction. In fact, one of the most creative uses of induction can be found in Cauchy’s proof of the AM-GM inequality in Cours d’analyse.
Consider the \(4!\) possible permutations of the numbers \(1,2,3,4\). Which of those permutations keep the expression \(x_1x_2+x_3x_4\) the same?
Show that if \(1+3+5+7+...+97+99=50^2\), then \(1+3+5+7+...+97+99+101=51^2\). Don’t forget that \((a+b)^2=a^2+2ab+b^2\).
Prove that for all positive integers \(n\) there exists a partition of the set of positive integers \(k\le2^{n+1}\) into sets \(A\) and \(B\) such that \[\sum_{x\in A}x^i=\sum_{x\in B}x^i\] for all integers \(0\le i\le n\).
Diophantine equations are those where we’re only interested in finding the integer solutions. Some of these equations are quite simple, while others look simple but are actually very difficult. The most famous one is Fermat’s Last Theorem, which says that when \(n>2\), there are no solutions to \[x^n+y^n=z^n.\] Pierre de Fermat claimed that he proved this in 1637, scribbling it in the margin of a book, but said “I have discovered a truly marvelous proof of this, which this margin is too narrow to contain." It was only proved by Andrew Wiles in 1995. Today’s problems won’t take 358 years to solve.
For which \(n\) is the expression \(4^n+n^4\) prime?
Find all solutions to \(x^2+2=y^3\) in the natural numbers.