Common mistakes in induction

## Common mistakes in induction
            ---
            ## Structure of an inductive proof
            #### Theorem
            For all $n\in\mathbb N$, $Q(n)$.
            #### Proof structure
            …, so $Q(1)$.

Suppose that, for some $n\in\mathbb N$, $Q(n)$.
            Then…, so $Q(n+1)$.

Hence, by induction, for all $n\in\mathbb N$, $Q(n)$.   □
 
 ---
 ## Common mistake 1: No base case
 In inductive proof requires not just a step, but a base case too.
 #### Claim (incorrect theorem)
 For all $n\in\mathbb N$, $2^n\lt0$.
 #### Attempted proof
 Suppose that, for some $n\in\mathbb N$, $2^n\lt0$.
 Then $2^{n+1}=2\times 2^n \lt 2 \times 0 = 0$.

Hence, by induction, for all $n\in\mathbb N$, $2^n\lt0$.   □
 
 ---
 ## Common mistake 1: No base case
 In inductive proof requires not just a step, but a base case too.
 #### Claim (incorrect theorem)
 For all $n\in\mathbb N$, $2^n\lt0$.
 #### Attempted proof
 Suppose that, for some $n\in\mathbb N$, $2^n\lt0$.
 Then $2^{n+1}=2\times 2^n \lt 2 \times 0 = 0$.

Hence, by induction, for all $n\in\mathbb N$, $2^n\lt0$.   □

The inductive step is perfect, but there is no base case, so the conclusion is invalid.
 
 ---
 ## Common mistake 1: No base case
 In inductive proof requires not just a step, but a base case too.
 #### Claim (incorrect theorem)
 For all $n\in\mathbb N$, $2^n\lt0$.
 #### Attempted proof
 Suppose that, for some $n\in\mathbb N$, $2^n\lt0$.
 Then $2^{n+1}=2\times 2^n \lt 2 \times 0 = 0$.

Hence, by induction, for all $n\in\mathbb N$, $2^n\lt0$.   □

The inductive step is perfect, but there is no base case, so the conclusion is invalid.

This proof can't be fixed, as the claim is false.
 
 ---
 ## Common mistake 2: Wrong base case
 An inductive proof must have the right base case.
 #### Theorem
 For all nonegative integers $n$, $n^2-3n$ is even.
 #### Attempted proof
 If $n=1$, then $n^2-3n=1^2-3=-2$, which is even.

Suppose $n$ is an integer such that $n^2-3n$ is even.
            Then $$(n+1)^2-3(n+1)=n^2+2n+1-3n-3=[n^2-3n] + 2(n - 1),$$ which is also even, by the inductive hypothesis.

Hence, by induction, for all $n\in\mathbb N$, $n^2-3n$ is even.   □
 
 ---
 ## Common mistake 2: Wrong base case
 An inductive proof must have the right base case.
 #### Theorem
 For all nonegative integers $n$, $n^2-3n$ is even.
 #### Attempted proof
 If $n=1$, then $n^2-3n=1^2-3=-2$, which is even.

Suppose $n$ is an integer such that $n^2-3n$ is even.
            Then $$(n+1)^2-3(n+1)=n^2+2n+1-3n-3=[n^2-3n] + 2(n - 1),$$ which is also even, by the inductive hypothesis.

Hence, by induction, for all $n\in\mathbb N$, $n^2-3n$ is even.   □

The proof is missing case $n=0$, which is included in the theorem.
 Fix it by changing the base case to $n=0$.
 
 ---
 ## Common mistake 2: Wrong base case
 An inductive proof must have the right base case.
 #### Theorem
 For all nonegative integers $n$, $n^2-3n$ is even.
 #### Corrected proof
 If $n=0$, then $n^2-3n=0^2-0=0$, which is even.

Suppose $n$ is an integer such that $n^2-3n$ is even.
            Then $$(n+1)^2-3(n+1)=n^2+2n+1-3n-3=[n^2-3n] + 2(n - 1),$$ which is also even, by the inductive hypothesis.

Hence, by induction, for all $n\in\mathbb N_0$, $n^2-3n$ is even.   □
 
 ---
 ## Common mistake 3: Too few base cases
 An inductive proof must have enough base cases.

Eg: Let the sequence $(a_n)\_\{n=1\}\^\infty$ be defined by $a_1=7$, $a_2=-1$, $a\_\{n+2\}=a\_\{n+1\}+2a_n$.
            #### Theorem
            For all nonegative integers $n$, $a_n=2^n-5(-1)^n$.
            #### Attempted proof
            We know $a_1=7$, and $2^1-5(-1)^1=7$.

Suppose $n$ is an integer such that $a_n=2^n-5(-1)^n$ and $a\_\{n+1\}=2\^\{n+1\}-5(-1)\^\{n+1\}$.

Then $a\_\{n+2\} = a\_\{n+1\}+2a_n = 2\^\{n+1\}-5(-1)\^\{n+1\} + 2(2^n-5(-1)^n) = \ldots = 2\^\{n+2\}-5(-1)\^\{n+2\}$.

Hence, by induction, for all $n\in\mathbb N$, $a_n=2^n-5(-1)^n$.   □
 
 ---
 ## Common mistake 3: Too few base cases
 Eg: Let the sequence $(a_n)\_\{n=1\}\^\infty$ be defined by $a_1=7$, $a_2=-1$, $a\_\{n+2\}=a\_\{n+1\}+2a_n$.
 #### Theorem
 For all nonegative integers $n$, $a_n=2^n-5(-1)^n$.
 #### Attempted proof
 We know $a_1=7$, and $2^1-5(-1)^1=7$.

Suppose $n$ is an integer such that $a_n=2^n-5(-1)^n$ and $a\_\{n+1\}=2\^\{n+1\}-5(-1)\^\{n+1\}$.

Then $a\_\{n+2\} = a\_\{n+1\}+2a_n = 2\^\{n+1\}-5(-1)\^\{n+1\} + 2(2^n-5(-1)^n) = \ldots = 2\^\{n+2\}-5(-1)\^\{n+2\}$.

Hence, by induction, for all $n\in\mathbb N$, $a_n=2^n-5(-1)^n$.   □

Step cannot be applied.
            We only know $Q(1)$, but hypothesis requires $Q(n)$ and $Q(n+1)$.

Fix by supplementing the base.
 
 ---
 ## Common mistake 3: Too few base cases
 Eg: Let the sequence $(a_n)\_\{n=1\}\^\infty$ be defined by $a_1=7$, $a_2=-1$, $a\_\{n+2\}=a\_\{n+1\}+2a_n$.
 #### Theorem
 For all nonegative integers $n$, $a_n=2^n-5(-1)^n$.
 #### Correct proof
 We know $a_1=7$, and $2^1-5(-1)^1=7$.

Also, $a_2 = -1$, and $2^2 - 5(-1)^2 = -1$.

Suppose $n$ is an integer such that $a_n=2^n-5(-1)^n$ and $a\_\{n+1\}=2\^\{n+1\}-5(-1)\^\{n+1\}$.

Then $a\_\{n+2\} = a\_\{n+1\}+2a_n = 2\^\{n+1\}-5(-1)\^\{n+1\} + 2(2^n-5(-1)^n) = \ldots = 2\^\{n+2\}-5(-1)\^\{n+2\}$.

Hence, by induction, for all $n\in\mathbb N$, $a_n=2^n-5(-1)^n$.   □
 
 ---
 ## Common mistake 4: Inductive hypothesis is "for all $n$"
 If you assume "for all $n\in\mathbb N$, $Q(n)$", then you can't prove $Q(n+1)$.

#### Theorem
            For all $n\in\mathbb N$, $Q(n)$.
            #### Attempted proof
            …, so $Q(1)$.

Suppose that, for all $n\in\mathbb N$, $Q(n)$.
            Then…, so $Q(n+1)$.

Hence, by induction, for all $n\in\mathbb N$, $Q(n)$.   □
 
 ---
 ## Common mistake 4: Inductive hypothesis is "for all $n$"
 If you assume "for all $n\in\mathbb N$, $Q(n)$", then you can't prove $Q(n+1)$.

#### Theorem
            For all $n\in\mathbb N$, $Q(n)$.
            #### Attempted proof
            …, so $Q(1)$.

Suppose that, for all $n\in\mathbb N$, $Q(n)$.
            Then…, so $Q(n+1)$.

Hence, by induction, for all $n\in\mathbb N$, $Q(n)$.   □

The step fails, because it begins with the hypothesis "$Q(1)$, $Q(2)$, $Q(3)$,…are all true"

With that assumption, proving $Q(n+1)$ is meaningless; it was already assumed!

---
 ## Common mistake 4: Inductive hypothesis is "for all $n$"
 If you assume "for all $n\in\mathbb N$, $Q(n)$", then you can't prove $Q(n+1)$.

#### Theorem
            For all $n\in\mathbb N$, $Q(n)$.
            #### Attempted proof
            …, so $Q(1)$.

Suppose that, for all $n\in\mathbb N$, $Q(n)$.
            Then…, so $Q(n+1)$.

Hence, by induction, for all $n\in\mathbb N$, $Q(n)$.   □

The step fails, because it begins with the hypothesis "$Q(1)$, $Q(2)$, $Q(3)$,…are all true"

With that assumption, proving $Q(n+1)$ is meaningless; it was already assumed!

Fix it be changing "for all" to "for some" in the inductive hypothesis.

#### Theorem
            For all $n\in\mathbb N$, $Q(n)$.
            #### Corrected proof
            …, so $Q(1)$.

Suppose that, for some $n\in\mathbb N$, $Q(n)$.
            Then…, so $Q(n+1)$.

Hence, by induction, for all $n\in\mathbb N$, $Q(n)$.   □