Mistakes in induction proofs

Two sequences are defined by the same rule, $\displaystyle {a_{n+1}}={a_n+2}$ and $\displaystyle {b_{n+1}}={b_n+2}$, but $\displaystyle {a_1}={1}$ and $\displaystyle {b_1}={2}$.

• The inductive step holds: if $\displaystyle {a_k}={b_k}$, then $\displaystyle {a_{k+1}}={a_k+2}={b_k+2}={b_{k+1}}$.
• The base case fails: $\displaystyle a_1\neq b_1$.
• And the sequences are indeed different: $\displaystyle 1, 3, 5, \ldots$ and $\displaystyle 2, 4, 6, \ldots$ – they have no term in common.

Another example: $\displaystyle {a_n}={1+2+\ldots+n}$ and $\displaystyle {b_n}={\frac{n^2}{2}+\frac{n}{2}+\frac{1}{2}}$. If $\displaystyle {a_k}={b_k}$, then $\displaystyle {a_{k+1}}={b_k+k+1}={b_{k+1}}$ – the step works. But $\displaystyle {a_1}={1}$ and $\displaystyle {b_1}={\frac{3}{2}}$, and in fact $\displaystyle {b_n}={a_n+\frac{1}{2}}$ always.

Two sequences: $\displaystyle {a_1}={b_1}={2}$, $\displaystyle {a_{n+1}}={2a_n}$ and $\displaystyle {b_{n+1}}={b_n+2n}$.

• $\displaystyle a_n$: $\displaystyle 2, 4, 8, 16, \ldots$; $\displaystyle b_n$: $\displaystyle 2, 4, 8, 14, \ldots$
• The first three terms are equal, and the fourth is not.
• A common start – even a long one – does not prove that two sequences are equal. Without the inductive step there is no proof.

“Proof”: “Assume the claim holds for every natural $\displaystyle n$. Then in particular it holds for $\displaystyle k+1$, so it holds for every $\displaystyle n$.”

• This is no proof: the assumption is exactly the claim to be proved.
• The induction hypothesis is about one $\displaystyle k$, and it is used to prove the claim for $\displaystyle k+1$ – the claim for $\displaystyle k+1$ is not assumed.

• Was the base case checked, and does it hold?
• Is the induction hypothesis about one $\displaystyle k$, and is what must be proved for $\displaystyle k+1$ written?
• Is every move in the inductive step right, and is the hypothesis used?
• Does the proof arrive exactly at the claim for $\displaystyle k+1$?
• Is the conclusion written?

Danny wrote: “The claim: $\displaystyle {1+5+9+\ldots+(4n-3)}={2n^2-n+1}$. Assume the claim holds for $\displaystyle k$. Then $\displaystyle {1+5+\ldots+(4k-3)+(4k+1)}={2k^2-k+1+4k+1}={2(k+1)^2-(k+1)+1}$, so the claim holds for every $\displaystyle n$.”

Check Danny’s working in the card.

What is missing in the proof? Is the claim true? What is the right formula for the sum?

Michal wrote: “The claim: $\displaystyle n^2+5n$ is odd for every natural $\displaystyle n$. Assume that $\displaystyle k^2+5k$ is odd. $\displaystyle {(k+1)^2+5(k+1)}={(k^2+5k)+2k+6}$, which is odd plus even – odd. So the claim holds.”
Find the mistake. Is the claim true?

On a circle $\displaystyle n$ points are marked and every two are joined by a chord, so that no three chords pass through one point. The numbers of parts of the disc for $\displaystyle {n}={1, 2, 3, 4, 5}$: $\displaystyle 1, 2, 4, 8, 16$.
Yoav claims that the number of parts is $\displaystyle 2^{n-1}$ for every $\displaystyle n$. For $\displaystyle {n}={6}$ there are 31 parts. What is wrong with the way Yoav reached his claim?

Ron wrote: “The claim: $\displaystyle 3^n-1$ is divisible by 4 for every natural $\displaystyle n$. Assume that $\displaystyle {3^k-1}={4m}$. $\displaystyle {3^{k+1}-1}={3(3^k-1)+2}={12m+2}$. So the claim holds.”

Check the move $\displaystyle {3^{k+1}-1}={3(3^k-1)+2}$ in the card.

Is $\displaystyle 12m+2$ divisible by 4? Find all of Ron’s mistakes, and check the claim for $\displaystyle {n}={1}$ and $\displaystyle {n}={2}$.