Learn

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:

(n+1)+n+(n1)=3n(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:

(n+1)+n+(n1)=3n(n+1) + n + (n-1) = 3n

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

(k+1)+k+(k1)=3k(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.

Instructions

1.

Create a variable called first and set it equal to your guess as to what the first base case should be in the code editor.

2.

Create another variable called second and set it equal to your guess as to what the second base case should be in the code editor.

3.

Finally, create a new variable called third and set it equal to your guess as to what the third base case should be in the code editor.

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?