Numbers and Sets | Part IA, 2001

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 nn, that 9n2n(mod7)9^{n} \equiv 2^{n}(\bmod 7) for all n1n \geq 1.

What is wrong with the following argument?

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

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

i=1m+1i=m(m+1)/2+m+1+126=(m+1)(m+2)/2+126\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.