Have 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 your code works to your boss or new client!

Mathematicians believe in the same idea: a mathematical proof is a mathematical explanation of why a statement (or conjecture) is either true or false. Induction is one method of proving statements, and an induction proof is a mathematical proof using induction. There are two induction methods: mathematical induction and strong induction. These two methods will be defined and demonstrated over the next few exercises.

Some statements (which we will prove via induction) include symbols that you may not have seen before. For instance, suppose we have the expression:

$\sum_{i=1}^5 i$

The Greek letter Sigma represents summation, or the adding of consecutive terms. The bottom number (i = 1) indicates where to start, and the top number (5) tells us where to stop. At each term i, we add that term operated on by the inside of the summation (in this case, i) onto the terms before it. In other words, this expression tells us to perform the operation 1 + 2 + 3 + 4 + 5. Here is another example:

$\sum_{i=0}^n 2i$

Here, we are adding the terms 2i from i=0 to some arbitrary number n. In other words, we are adding

$2(0) + 2(1) + 2(2) + \cdots + 2(n-1) + 2(n).$

Hopefully seeing this will clear things up for when summation appears later in this lesson!

For now, though, try adding the odd positive integers together, starting with the first two and increasing the number of odds you are adding together by one until you have computed the sum of the first four positive odd numbers. You might see a pattern develop!