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:

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

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

i+1k+1(2i1)=2(k+1)1+i=1k2i1\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+1th 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:

i=1k+1(2i1)=2(k+1)1+k2\sum^{k+1}_{i=1} (2i - 1) = 2(k+1) - 1 + k^2

The rest is left to basic algebra:

2(k+1)1+k2=k2+2k+21=k2+2k+1=(k+1)22(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+1th case is true.



Recall that in the previous exercise we set k equal to nine. Now, set k equal to 10 in the code editor.

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?