Stephanie M. answered • 05/18/15

Private Tutor - English, Mathematics, and Study Skills

Induction involves three steps. We'll follow each of them now...

1. PROVE IT'S TRUE FOR THE BASE CASE (n = 1)

n = 1 is the lowest possible value for n. So, plug that in and see if it makes the statement true:

n(n

^{2}- 1)(n + 2)(1)((1)

^{2}- 1)((1) + 2)(1)(1 - 1)(3)

1(0)(3)

0

0 is indeed divisible by 4. So, we've proven it's true in the base case.

2. ASSUME IT'S TRUE FOR THE CASE n - 1

That means we're going to assume that (n - 1)((n - 1)

^{2}- 1)((n - 1) + 2) is divisible by 4. Let's make that expression a bit simpler...(n - 1)(n

^{2}- 2n + 1 - 1)(n + 1)(n - 1)(n

^{2}- 2n)(n + 1)(n - 1)(n + 1)(n

^{2}- 2n)(n

^{2}- n + n - 1)(n^{2}- 2n)(n

^{2}- 1)(n^{2}- 2n)n

^{4}- 2n^{3}- n^{2}+ 2nSo, that expression is divisible by 4, by assumption.

3. PROVE IT'S TRUE FOR n, GIVEN THAT IT'S TRUE FOR n - 1

So, now we'd like to prove that n(n

^{2}- 1)(n + 2) is divisible by 4. Let's simplify that a bit...(n

^{3}- n)(n + 2)n

^{4}+ 2n^{3}- n^{2}- 2nThat looks a lot like something we've assumed is divisible by 4: n

^{4}- 2n^{3}- n^{2}+ 2nWe're missing the -2n

^{3}and the +2n, though, so let's subtract 2n^{3}and add 2n. To make sure I haven't changed the expression's value at all, I'll also add 2n^{3}and subtract 2n elsewhere:n

^{4}- 2n^{3}+ 2n^{3}+ 2n^{3}- n^{2}+ 2n - 2n - 2nThose red terms cancel each other out, and the rest is just the same expression we had before. So, let's rearrange that a bit:

(n

^{4}- 2n^{3}- n^{2}+ 2n) + 2n^{3}+ 2n^{3}- 2n - 2n(n

^{4}- 2n^{3}- n^{2}+ 2n) + 4n^{3}- 4n(n

^{4}- 2n^{3}- n^{2}+ 2n) + 4(n^{3}- n)Our assumption says that the first parenthetical portion is definitely divisible by 4, since that's the n - 1 case. And the second portion is definitely divisible by 4, since it's a multiple of 4 (I could factor 4 out). So, the entire expression is indeed some multiple of 4 plus some multiple of 4, which is divisible by 4.

We've therefore proven it's true in the n case.

And that's the end of our proof! By induction, the expression is divisible by 4 for any n ≥ 1.

This works because we've done the following:

(a) We proved that, assuming it's true for one case, it's true for the next case (STEP 3)

(b) We proved that it's true for the first case (STEP 1)

So, since it's true for the first case and for any case that follows a true case, it's true for every case.

Stephanie M.

tutor

Hi Makayla,

That's a great question. The short answer is, yes, the following two methods are equivalent:

(a) Assume it's true for n, and prove it's true for n+1

(b) Assume it's true for n-1, and prove it's true for n

That's because both serve the same function. We just want to prove that, given that one case is true, we could prove the next case is true. I used (b), but you're absolutely free to use (a). It will likely look pretty much the same.

Sometimes, it's easier to use one method or the other. Pick the one you like best and use that most of the time, but remember that you can always try the other method if the expression gets too hard to work with!

Does that make sense?

Stephanie

P.S.

Here's method (a), briefly:

**Assume it's true for n**: n

^{4}+ 2n

^{3}- n

^{2}- 2n is divisible by 4

**Prove it's true for n+1**, which simplifies to: n

^{4}+6n

^{3}+ 11n

^{2}+ 6n

That's equivalent to n

^{4}+ 2n^{3}- 2n^{3}+ 6n^{3}- n^{2}+ n^{2}+ 11n^{2}- 2n + 2n + 6nThat's equivalent to (n

^{4}+ 2n^{3}- n^{2}- 2n) - 2n^{3}+ 6n^{3}+ n^{2}+ 11n^{2}+ 2n + 6nThat's equivalent to (n

^{4}+ 2n^{3}- n^{2}- 2n) + 4n^{3}+ 12n^{2}+ 8nAll of those expressions are divisible by 4, so the statement is true for the n+1 case.

Report

05/18/15

Makayla R.

That does make sense! Thank you so much!

Report

05/19/15

Makayla R.

^{2}-1)(k+2) is divisible by 4" is true), and then show that if P(k) is true that P(k+1) is true. Is k+1 the same as using k-1?05/18/15