Mathematical Induction

**Jacko** · August 9th 2007, 02:18 AM

- If n is a positive odd integer, show that n^2+3 is divisible by 4 ~ dont know whether to do this by congruence or mathematical induction

- Use mathematical induction to prove that 3|(n^3-4n+6) for all positive integers n
Any help is appreciated!

**Soroban** · August 9th 2007, 05:59 AM

Hello, Jacko!

If $n$ is a positive odd integer, show that $n^2+3$ is divisible by 4

If you don't have to use induction, an algebraic proof is faster.

Let $n \:=\:2a-1$ for some positive integer $a$ .

Then: . $n^2+3\;=\;(2a-1)^2 + 3 \;=\;4a^2 + 4a + 1 + 3\;=\;4a^2 + 4a + 4 \;=\;4(a^2 + a + 1)$

Therefore: . $n^2 + 3$ is divisible by 4.

Use induction to prove: . $3|(n^3-4n+6)$ for all positive integers $n$

$S(1)\!:\;1^3 - 4\cdot1 + 6 \:=\:3$ . . . yes!

Assume $S(k)\!:\;\;k^3 - 4k + 6 \:=\:3m$ .for some integer $m$

Add $3k^2 + 3k + 1$ to both sides:
. . $k^3 \,{\color{blue}+\, 3k^2 + 3k + 1}\, - 4k + 6 \:=\:3m\, {\color{blue}+\, 3k^2 + 3k + 1}$

Subtract 4 from both sides:
. $(k+1)^3 - 4k \,{\color{blue}- \,4} + 6 \:=\:3m + 3k^2 + 3k + 1 \,{\color{blue}- \,4}$

And we have: . $(k+1)^3 - 4(k+1) + 6 \:=\:3(m + k^2 + k - 1)$

The left side is the left side of $S(k\!+\!1)$
The right side is divisible by 3.

The inductive proof is complete.

**Jacko** · August 12th 2007, 01:57 AM

Thank you so much Soroban!!
I just have one question, why do you add 3k^2+3k+1 to both sides in the inductive question?
Thanks again!

**topsquark** · August 12th 2007, 03:45 AM

Originally Posted by Jacko

Thank you so much Soroban!!
I just have one question, why do you add 3k^2+3k+1 to both sides in the inductive question?
Thanks again!

He's trying to make the $k^3$ term go to $(k + 1)^3$ .

Here's a slightly different way:
We wish to show that 3 divides $n^3 - 4n + 6$ for all (positive integer) values of n.

So try n = 0: $0^3 - 4 \cdot 0 + 6 = 6$
This is divisible by 3, so the theorem is true for this case.

So now assume the theorem is true for some n = k. We wish to show the theorem is also true for n = k + 1.

So we need to show that 3 divides $(k + 1)^3 - 4(k + 1) + 6$ given that 3 divides $k^3 - 4k + 6$ .

So look at $(k + 1)^3 - 4(k + 1) + 6$ :
$(k + 1)^3 - 4(k + 1) + 6$

$= (k^3 + 3k^2 + 3k + 1) - (4k + 4) + 6$

$= k^3 + 3k^2 + 3k + 1 - 4k - 4 + 6$

$= k^3 + 3k^2 - k + 3$

Now, I want to make this expression a bit simpler by reducing the number of terms in it. One way to do this is to subtract out a multiple of 3. (If we can show that a number "a - 3m" is divisible by 3 then we will have shown that "a" is also divisible by 3.)

One handy thing to know about using Mathematical Induction is that the theorem itself that we are trying to prove comes in handy. We know that $k^3 - 4k + 6$ is divisible by 3 (that's our assumption.) So I'm going to subtract this from our other expression. If the result is divisible by 3, then so is our original expression.
$(k^3 + 3k^2 - k + 3) - (k^3 - 4k + 6)$

$= 3k^2 + 3k - 3 = 3(k^2 + k - 1)$

Since this expression is divisible by 3 then so is
$k^3 + 3k^2 - k + 3 = (k + 1)^3 - 4(k + 1) + 6$

So the theorem is true for n = k + 1. Therefore etc.

-Dan

Thread: Mathematical Induction

LinkBack

Thread Tools

Display