4.II.8E

What is the Principle of Mathematical Induction? Derive it from the statement that every non-empty set of positive integers has a least element.

Prove, by induction on $n$, that $9^{n} \equiv 2^{n}(\bmod 7)$ for all $n \geq 1$.

What is wrong with the following argument?

"Theorem: $\sum_{i=1}^{n} i=n(n+1) / 2+126$.

Proof: Assume that $m \geq 1$ and $\sum_{i=1}^{m} i=m(m+1) / 2+126$. Add $m+1$ to both sides to get

$\sum_{i=1}^{m+1} i=m(m+1) / 2+m+1+126=(m+1)(m+2) / 2+126$

So, by induction, the theorem is proved."

*Typos? Please submit corrections to this page on GitHub.*