Lesson 3

As we have seen, some statements are more conveniently proven using complete induction. It may seem that complete induction is a more powerful method. In fact, this is not the case: if the statement “\(A(n)\) is true for all integers \(n \ge 1\)” can be proven by complete induction, then it can also be proven by standard induction. For this, it suffices to prove the statement “\(B(n)\) is true for all integers \(n \ge 1\)” by standard induction, where \(B(n)=A(1) \land \dotsb \land A(n)\) (in other words, \(B(n)\) is true if and only if all \(A(1), \dotsc, A(n)\) are true).