TAOCP: Volume 1, Chapter 1 - Basic Concepts, 1.2.1 Mathematical Induction

27 Jun 2022

Summary

Section 1.2.1 defines mathematical induction by contrasting it to inductive reasoning and by providing examples of both.

Key Takeaway

Mathematical induction is different from inductive reasoning. Basically, you can prove that a procedure is true, make an assumption about the rest of the outputs, and then prove that assumption.

Notes

Mathematical induction is concept for proving that if a procedure, or equation, P(n) is true for all positive integers n, you can prove that P(1) is true, and also that P(n+1) is true. The P(n+1) part if the induction. It is something that you believe to be true. It is something that you worked out long hand and found to be reasonable true.

Knuth writes a very large proof for the previously presented Algorithm E (Extended Euclid’s algorithm). This one is nuts and I followed none of it. This goes on for 2 pages.

There was so much math. Knuth offers a way out for the sake of motivation allowing the reader to skim this chapter. After studying for 2 hours, and re-reading many times, I still could not understand the math. I get the induction part, which is what I think the purpose of the section truly is.

I took the out and accepted the skim.

Exercises

I remember being in college and taking a final exam where I could not even understand the questions. Oddly enough this was for a course in my field of study.

There were 15 exercises in this section. The most difficult being a level HM28. I felt like I was sitting in that lecture hall again reading and rereading that test. I was looking for an out and did not have one. Thankfully Knuth gave me one. No exercises were completed.

< back