Non-Standard Induction

In standard induction, the most important part is the inductive step where you show that if a statement is true for some natural number \(k\), then it is also true for \(k+1\). The base case, albeit important, is obvious most of the time. In other words, proving something by induction requires linking \(P(k)\) to \(P(k+1)\) in some way. But what if you can't do that? What if you somehow showed that \(P(k)\Rightarrow P(k+m)\). 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 \(=1\) and \(P(k)\implies P(k+1)\). 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 \(P(k)\Rightarrow P(k+m)\).

Proof by Non-Standard Induction

• Step \(1\): Prove the base case:
  This is where you verify that the statement is true for \(1\), \(2\), \(3\), \(\cdots m\)
• Step \(2\): The inductive step:
  Now you show that \(P(k)\Rightarrow P(k+m)\). In other words, you show that if \(P(k)\) were true, so would be \(P(k+m)\).

If you manage to do both of these things, you'll have ensured that the statement is true for all positive integers \(n\). Sometimes it is easier to do step 2 first, as playing around with the problem allows us to naturally discover a suitable \(m\) value.

This approach is often useful when you see a cyclic term, like \( (-1)^n \), \( \sin ( \frac{ n \pi } { 5 }) \) or \( n^2 \pmod{5} \), 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 \( n > 7 \) can be written as \( 3 a + 5 b \) for some non-negative integers \(a\) and \(b\).

---

If we know that the integer \(k \) can be written in the form \( 3a + 5b \), then it is clear that \( k + 3 = 3 ( a+1) + 5b \) can also be written in the required format. As such, this tells us that we should try to apply non-standard induction with \( m = 3 \).

To prove the base case, observe that:

\[\begin{align} 8 &= 3 \times 1 + 5 \times 1 \\ 9 &= 3 \times 3 + 5 \times 0 \\ 10 &=3 \times 0 + 5 \times 2. \end{align}\]

Hence, by non-standard induction, the statement is true for all integers \( n > 7 \). \(_\square\)

Note: This is a special case of the Chicken Mcnugget Theorem.

Prove that for any integer \(n>5\), every square can be divided into \(n\) smaller squares.

---

A good approach to this problem is noticing that any square can be divided into \(4\) smaller squares.

Imgur

This means if a square can be divided into \(k\) smaller squares, then the square can be divided into \(k+3\) squares. As such, this tells us that we should try to apply non-standard induction with \( m = 3 \).

Now if we want to prove the statement for any integer \(n>5\), we need to show that the statement holds for \(n=6, 7, 8\). 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.

Imgur

That covers our base cases and completes the proof. \(_\square\)

[Erdos & Suranyi] Prove that every positive integer can be written in the form \(\pm 1^2\pm 2^2\pm 3^2\pm \cdots \pm l^2\) for some positive integer \(l\) and the appropriate choices of plus and minus signs.

---

First, we make the (clever) observation that \( (a+1) ^2 - ( a + 2)^2 - (a+3) ^2 + (a+4) ^2 = 4 \). 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 \(k=±1^2 ± 2^2±3^2\pm ... ± l^2\), then \(k+4=±1^2 ± 2^2±3^2\pm ... ± l^2 +(l+1)^2- (l+2)^2 - (l+3)^2 + (l+4)^2\). As such, this tells us that we should try to apply non-standard induction with \( m = 4 \).

Now the only thing left to do is show that such representations exist for integers \(1\) through \(4\). After playing around for a while we see that

\[ \begin{align} 1 & =1^2\\ 2& =-1^2-2^2-3^2+4^2 \\ 3 &=-1^2+2^2 \\ 4 & =-1^2-2^2+3^2. \end{align} \]

This means the statement holds for all positive integers. \(_\square\)

Note: The expression that we found is not necessarily the shortest. For example, we have \( 5 = 1^2 + 2 ^2 \), though our induction step will give us \( 5 = 1^2 + 2^2 - 3^2 - 4^2 + 5^2 \). 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 \(m > 1 \), and let \(S\) be a set of positive integers with the following properties:

\(\quad\) (1) The integers \(1, 2, \ldots , m \) belong to the set.
\(\quad\) (2) Whenever an integer \(k\) is in \(S\), the integer \(k+m\) must also be in \(S\).

Then \(S\) is the set of all positive integers. \(_\square\)

We will prove this theorem by contradiction.

Let \(T\) be the set of all positive integers not in \(S\). By assumption, \(T\) is non-empty. Hence it must contain a smallest element, which we will denote by \(\alpha\). Then by (1), \(0 < \alpha- m < \alpha\).

Since \( \alpha\) is the smallest integer in \(T\), this implies that \( \alpha-m \not\in T \Rightarrow(\alpha-m)\in S \). By (2), \(S\) must also contain \( (\alpha-m)+m=\alpha\). This contradicts the assumption that \(\alpha\subset\) \(T\).

Hence set \(T\) is empty, and set \(S\) contains all positive integers. \(_\square \)

1) Prove the following using non-standard induction with \(m = 5 \):

• Show that every integer \( n > 7 \) can be written as \( 3 a + 5 b \) for some non-negative integers \( a, b \).

2) If \( \omega \) is a complex third root of unity, what is the value of \( \omega^{2n} + \omega^n + 1 \)?

3) Evaluate \(\displaystyle \sum_{k=0 } ^ { \lfloor \frac{n}{3} \rfloor } { n \choose 3k } \).