# 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.

## Formulation

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.

## Examples

## 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.

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.

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.

## Proof of Non-standard Induction

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 \)

## Additional Problems

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 } \).

**Cite as:**Non-Standard Induction.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/non-standard-induction/