Induction Proofs Discussion

(The following is/are the initial prompt(s) for an online discussion; students may have posted responses, and prompts for further discussion may have been added, but these things are not shown.)

Induction is a powerful but not necessarily intuitive proof method. This discussion gives you a chance to start practicing it.

I claim that the sum of the first n even natural numbers is equal to n(n+1). In slightly more mathematical notation, my claim is that sums of the form 2 + 4 + 6 + … + 2n are equal to n(n+1), or even more formally,

\[\sum_{i=1}^n 2i = n(n+1)\]

Discuss how you could use induction to prove this. For example, what would the basis step be? What would the inductive step need to show? What would you assume at the beginning of the inductive step? How might you proceed to prove the inductive step from that assumption?

And here’s another question about inductive sets that came up as I was finishing the notes from Friday’s class, and that makes a good discussion topic about inductive sets: do you think the empty set is inductive? Why or why not?