5.2Prove by induction on that for .

Proof:We use induction on . Base case: For , and and so . Inductive step: Suppose now as inductive hypothesis that for some . Then (by induction hypothesis). So we will have proved that if we can prove that . But , and since , so that . Hence and so we have deduced that as required to complete the inductive step. Conclusion: Hence, by induction, for all .