# Math Help - Finite induction???

1. ## Finite induction???

I have a example problem that I can't figure out.

We have listed in adjacent collumns the values of 4n and n^2 - 7 for the positive integers n, where 1 <= n <= 8

n |4n| n^2-7
1 | 4 | -6
2 | 8 | -3
3 | 12 | 2
4 | 16 | 9
5 | 20 | 18
6 | 24 | 29
7 | 28 | 42
8 | 32 | 57

From the table, we see that (n^2 - 7) < 4n for n = 1,2,3,4,5 but when n=6,7,8, we have 4n < (n^2-7). These last three observations lead us to conjecture: For all n>=6 4n < (n^2 - 7)

Let S(n) denote the open statement 4n < (n^2 - 7). Then table confirms that s(6) is true and we have our basis step.
In this example, the induction hypothesis is S(k): 4k < (k^2 - 7) where K is positive integer and K >= 6. In order to establish the inductive step, we need to obtain the truth of S(k + 1) frin that if s(k). That is, from 4k < (k^2-7) we must conclude that 4(k+1) < [(k+1)^2 - 7].
Here are the necessary steps

4k < (k^2 - 7) => 4k + 4 < (k^2 - 7) + 4 < (K^2 - 7) + (2k + 1)

(because for K >= 6, we find 2k+1 >= 13 > 4), and

4k + 4 < (K^2 - 7) + (2k+1) => 4(k+1) < (K^2 +2k + 1) - 7 = (k+1)^2-7

My question is where in the world do the numbers I bolded come from????

2. ## Induction

Hello bwhit132
Originally Posted by bwhit132
4k < (k^2 - 7) => 4k + 4 < (k^2 - 7) + 4 < (K^2 - 7) + (2k + 1)

(because for K >= 6, we find 2k+1 >= 13 > 4), and

4k + 4 < (K^2 - 7) + (2k+1) => 4(k+1) < (K^2 +2k + 1) - 7 = (k+1)^2-7

My question is where in the world do the numbers I bolded come from????
Welcome to Math Help Forum!

There are two answers to your question. The first answer is to do with how it works; the second is to do with why. The rule explaining the how is:

• We mayadd the same number to both sides of an inequality, and it remains true. In other words:

• $a

What's happened, then, is that 4 has been added to both sides of the inequality:

$4k

That was how the + 4 appeared.

But you may have asked: why should we want to add 4 to both sides of the inequality? The answer is that we need to create a term in $4(k+1)$ so that we can establish the truth of $S(k+1)$.

So that's why the + 4 appeared.

The same thing happens again in the next stage, although it's not so clear this time. Let me put things the other way round, and you'll see how it works.

$k\ge 6\Rightarrow 2k+1 \ge 13 \Rightarrow 2k+1 > 4$

So, writing this the other way around, we get:

$4 < 2k+1$ whenever $k\ge 6$

If we now add $(k^2-7)$ to both sides of $4 < 2k+1$, we get:

$(k^2-7) +4 <(k^2-7) +2k+1$

So that's the how. Now for the why. Why look at $2k+1$ at all? Well, it's to do with completing the square, because, again, we need to create a term in $(k+1)^2$ to establish the truth of $S(k+1)$.

And to make $k^2$ into $(k+1)^2$ we need to involve $2k+1$, because $(k+1)^2 = k^2+2k+1$.

Is that OK now?