In standard induction, the most important part is the inductive step where you show that if a statement is true for some natural number , then it is also true for . The base case, albeit important, is obvious most of the time. In other words, proving something by induction requires linking to in some way. But what if you can't do that? What if you somehow showed that . Can we use that to prove something?
The answer is yes. The induction argument is very flexible and it doesn't have to be restricted to the base case and . Non-standard induction refers to forms of induction that don't follow the 'regular' or 'standard' format.
Here's a way to prove a statement true for all positive integers, if you've managed to show that .
Proof by Non-Standard Induction
- Step : Prove the base case:
This is where you verify that the statement is true for , , ,
- Step : The inductive step:
Now you show that . In other words, you show that if were true, so would be .
If you manage to do both of these things, you'll have ensured that the statement is true for all positive integers . Sometimes it is easier to do step 2 first, as playing around with the problem allows us to naturally discover a suitable value.
This approach is often useful when you see a cyclic term, like , or , or when we spot a certain pattern in the sequence. This often makes the induction step simpler to show, though it means that we will have to consider multiple base cases.
Show that every integer can be written as for some non-negative integers and .
If we know that the integer can be written in the form , then it is clear that can also be written in the required format. As such, this tells us that we should try to apply non-standard induction with .
To prove the base case, observe that:
Hence, by non-standard induction, the statement is true for all integers .
Note: This is a special case of the Chicken Mcnugget Theorem.
Prove that for any integer , every square can be divided into smaller squares.
A good approach to this problem is noticing that any square can be divided into smaller squares.
This means if a square can be divided into smaller squares, then the square can be divided into squares. As such, this tells us that we should try to apply non-standard induction with .
Now if we want to prove the statement for any integer , we need to show that the statement holds for . If we can do that, we're done. (Why?)
This proves to be actually harder than showing the inductive step. But if you get your hands dirty a little bit, you'll see this.
That covers our base cases and completes the proof.
[Erdos & Suranyi] Prove that every positive integer can be written in the form for some positive integer and the appropriate choices of plus and minus signs.
First, we make the (clever) observation that . This can be arrived at by trying to get rid of the quadratic and linear terms, in order to arrive at a constant.
Hence, if , then . As such, this tells us that we should try to apply non-standard induction with .
Now the only thing left to do is show that such representations exist for integers through . After playing around for a while we see that
This means the statement holds for all positive integers.
Note: The expression that we found is not necessarily the shortest. For example, we have , though our induction step will give us . In this question, we are merely interested in the existence for a representation, and not concerned about finding the most compact representation.
This proof is very similar to the proof of standard induction. Can you spot the difference?
Fix an integer , and let be a set of positive integers with the following properties:
(1) The integers belong to the set.
(2) Whenever an integer is in , the integer must also be in .
Then is the set of all positive integers.
We will prove this theorem by contradiction.
Let be the set of all positive integers not in . By assumption, is non-empty. Hence it must contain a smallest element, which we will denote by . Then by (1), .
Since is the smallest integer in , this implies that . By (2), must also contain . This contradicts the assumption that .
Hence set is empty, and set contains all positive integers.
1) Prove the following using non-standard induction with :
- Show that every integer can be written as for some non-negative integers .
2) If is a complex third root of unity, what is the value of ?
3) Evaluate .