Learn how to prove mathematical statements using induction and strong induction.

Induction and Strong Induction: Lesson

Congratulations, 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_ supposes that our statement is true for some integer `k`, with the caveat that `k` must exceed the number set as the base case. 

Recall that we supposed that for any positive integer `n`:

```tex
\sum^n_{i=1} (2i-1) = n^2
```

Using the definition of induction hypothesis as well as the fact that we defined the base case as `k = 1` in the previous exercise, we can reword this conjecture to say this:
For some integer `k` in which `k > 1`:

```tex
\sum^k_{i=1} (2i-1) = k^2
```

We will use Python to code this hypothesis through the upcoming checkpoints. For convenience, we will set the variable `k` equal to nine.

Induction: Induction Hypothesis

Were you able to figure out that these sums created a pattern of 4, 9, 16, and 25, or n2? In fact, this turns out to be true for all of the positive odd integers: the sum of the first `n` odd integers does, in fact, equal n2. 

In mathematical symbols, what we are saying is that for all positive integers `n`:

```tex
\sum^n_{i=1} (2i-1) = n^2
```

Induction has important applications in the computer science industry, specifically in quality assurance and case-testing. When working at any programming job, you will need to test your code for every case imaginable in order to minimize the number of errors that could occur when the product releases. A good way to case-test your code is to determine if any case creates some kind of error upon execution or compilation.

How does this idea relate to induction? We will see in the upcoming checkpoints that we need `n` to be a positive integer in order for our conjecture to work. To show this, we will define a number `n` to be _nonnegative_ if `n` is an integer that is greater than or equal to zero and then we will suppose our conjecture is true for all nonnegative integers `n`. In other words, our new conjecture is this:

```tex
\sum^n_{i=0} (2i-1) = n^2
```

Applications of Induction

Congratulations on reaching the end of this lesson! Let’s recap what we have learned:

1. A _mathematical proof_ is a mathematical explanation of whether or not a given statement is true or false.
2. _Mathematical induction_ is a technique that proves a statement by providing one base case, assuming the statement is true for some larger integer `k`, then proving the statement is true for `k+1` using said assumption (induction hypothesis).
3. _Strong induction_ is a technique that proves a statement by providing more than one base case, assuming the statement is true for all integers from the largest base case to some even larger integer `k`, and then proving the statement is true for `k+1` using that assumption (induction hypothesis).

As a final check for understanding, the checkpoint that follows will test your ability to determine which statement requires which method. A statement will be provided below, and you will type your suggested method of proof in Python.


Review

Well 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:

```tex
(n+1) + n + (n-1) = 3n
```

You may think that the first step in proving this statement is to provide one base case. Unfortunately, that base case is not enough for our new example. Why? The big reason is this: our induction hypothesis currently assumes that our statement is true for some integer `k`. Recall that our conjecture is:

```tex
(n+1) + n + (n-1) = 3n
```

This means that our induction hypothesis is this: for some positive integer `k` which exceeds `n`,

```tex
(k+1) + k + (k-1) = 3k
```

If we were to prove this using induction on the left-hand side, then we would need our hypothesis to be true at `k-1` in order to use our induction hypothesis correctly. However, the current induction hypothesis states that the theorem is true at just `k`; thus, a new method of proof needs to be used.

These next two exercises (including this one) will help to formally define _strong induction_, the approach we need in proving statements like these. The first step to strong induction is to identify the base cases we need. For this problem, since we have the terms `n+1`, `n`, and `n-1` in our statement, we need three base cases to proceed.

Strong Induction: Multiple Base Cases

Now 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:

```tex
(n+1) + n + (n-1) = 3n
```

We noted in the previous exercise that we needed to modify our induction hypothesis so that the hypothesis is true at `k` and at `k-1`. We will fix this problem by supposing, for all integers between our largest base case (we saw from the last exercise that this is `n = 3`) and some integer `k`, that:

```tex
(k+1) + k + (k-1) = 3k
```

Now we have an induction hypothesis that is true at `k` and at `k-1`. (Note that we started our assumption from the largest base case because we have already proved the conjecture for each base case below our largest one, and so assuming their truth is unnecessary.)

Our task will be to prove that:

```tex
(k+2) + (k+1) + k = 3(k+1)
```

We will need to be creative with our left-hand expression. We know by the induction hypothesis that `(k+1) + k + (k-1) = 3k`. Why not force this into our left-hand side expression? We know that:

```tex
(k+2) + (k+1) + k = (k+1) + 1 + k + 1 + (k - 1) + 1 = (k+1) + k + (k-1) + 3
```

We can now use or induction hypothesis to substitute `3k` in for `(k+1) + k + (k-1)` to obtain:

```tex
(k+2) + (k+1) + k = 3k + 3
```

Finally, factor out a 3 from the right-hand side to obtain:

```tex
(k+2) + (k+1) + k = 3(k + 1)
```

Since we obtained our desired result, our proof is now complete.


Strong Induction: Induction Hypothesis

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:

```tex
\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:

```tex
\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

```tex
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!

Introduction to Proofs and Induction

Well 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 value we supposed in the induction hypothesis. For our example, we want to prove that:

```tex
\sum^{k+1}_{i=1} (2i-1) = (k+1)^2
```

We first will take a look at our sum and say that:

```tex
\sum^{k+1}_{i=1} (2i - 1) = 2(k+1) - 1 + \sum^k_{i=1} 2i - 1
```

In other words, we are saying that the sum of the odd integers from 1 to `k+1` equals the sum of the odd integers from 1 to `k` plus the `k+1`th odd integer. These two sums are both adding `k+1` odd integers together, and so we can confidently say that they mean the same thing.

Does the summation on the right look familiar? That’s because that is exactly the summation defined in our induction hypothesis! We can substitute k2 for that sum and obtain:

```tex
\sum^{k+1}_{i=1} (2i - 1) = 2(k+1) - 1 + k^2
```

The rest is left to basic algebra:

```tex
2(k+1) - 1 + k^2 = k^2 + 2k + 2 - 1 = k^2 + 2k + 1 = (k+1)^2
```

The result `(k+1)**2` is, in fact, what we sought in the beginning, and so our proof is now complete. Sadly, Python cannot mathematically prove these types of arguments for you. The best we can do using Python is to test if the `k+1`th case is true.

Induction: Proving the Inductive Step

We 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 first `n` odd integers is equal to n2. In other words:

```tex
\sum^n_{i=1} (2i-1) = n^2
```

How do we go about proving such a statement is really true for any positive integer `n`? We will use the principle of _mathematical induction_, the formal definition of which will be developed throughout these next couple of exercises.

The first step in any induction proof is to identify the _base case_ (the smallest possible case for which this statement is true). For instance, suppose you wanted to show for all positive integers `x` that `x` is at most x2, or

```tex
x \leq x^2
```

Since our cases are all of the positive integers, our base case (the smallest case) for this example is the smallest possible integer. That happens to be 1, and we can show that `1 <= 1**2` quite easily because `1 = 1**2`. Therefore, we have proven the base case for this conjecture. The upcoming checkpoint will ask you to find the base case for the statement

```tex
\sum^n_{i=1} (2i-1) = n^2,
```

which we established earlier in this narrative.