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{aligned} 8 &= 3 \times 1 + 5 \times 1 \\ 9 &= 3 \times 3 + 5 \times 0 \\ 10 &=3 \times 0 + 5 \times 2. \end{aligned}$

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{aligned} 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{aligned}$

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 }$.