Proofs
Learn about induction, strong induction, and other types of proofs.
Start
Induction and Strong Induction: Lesson
Lesson 1 of 1
- 1Have you ever answered a question correctly in class but couldn’t explain why it’s correct? The ability to effectively explain your arguments is a crucial skill to have when you are describing why …
- 2Were you able to figure out that these sums created a pattern of 4, 9, 16, and 25, or n 2 ? In fact, this turns out to be true for all of the positive odd integers: the sum of the first n odd integ…
- 3We saw in the previous exercise an example of testing our code to discover faulty cases. We can now properly define the statement we found in Exercise 1: For any positive integer n, the sum of the…
- 4Congratulations, we have completed the first step to our induction proof! Next comes the inductive step, which begins with our definition of the induction hypothesis. The induction hypothesis s…
- 5Well done! We now have written out our induction hypothesis both in writing and in Python code. Our final task is to prove that our induction hypothesis is true for the integer k+1, where k is the …
- 6Well done, we have completed the first induction example! Let’s try a different example. For any positive integer n, the number 3n actually does have an interesting property: (n+1) + n + (n-1) = 3…
- 7Now that we have our base cases, our next step is to fix our induction hypothesis. Recall that our statement we supposed in the previous exercise is the following: (n+1) + n + (n-1) = 3n We note…
How you'll master it
Stress-test your knowledge with quizzes that help commit syntax to memory