Induction

[diggsy]

I'm having a bit of a problem with proof by induction while going trough old tests in prep for my upcoming.

Prove with help of induction that n²-7n+12 is non negative for all integers n>=3.

First I get done with the base step by substituting n with 3 and get 3²-73+12 = 0

The problem step comes with the induction. I assume this function holds for n = k and will then prove k+1.

So (k+1)²-7(k+1)+12 = k²+2k+1-7k-7+12 = k²-5k+6
This doesn't feel right but I'm unable to tell where I've gone wrong and what has gone wrong.

 

[HallsofIvy]

I'm having a bit of a problem with proof by induction while going trough old tests in prep for my upcoming.

Prove with help of induction that n²-7n+12 is non negative for all integers n>=3.

First I get done with the base step by substituting n with 3 and get 3²-73+12 = 0

The problem step comes with the induction. I assume this function holds for n = k and will then prove k+1.

So (k+1)²-7(k+1)+12 = k²+2k+1-7k-7+12 = k²-5k+6

Complete the square:
k^2- 5k+ 25/4- 1/4= (k- 5/2)^2- 1/4. Since k>= 3, k- 5/2>= 1/2

This doesn't feel right but I'm unable to tell where I've gone wrong and what has gone wrong.

Nothing wrong, you just need to finish it.

 

[diggsy]

Complete the square:
k^2- 5k+ 25/4- 1/4= (k- 5/2)^2- 1/4. Since k>= 3, k- 5/2>= 1/2


Nothing wrong, you just need to finish it.

I fail to see how you get 25/4 -1/4 from also I dont see how anything has been proven, all I see is some fancy rewriting. A bit more on the how and why so I can understand and solve other problems and not just the solution to this problem.

Also why don't write (k- 5/2)^2 >= 1/4 ?

 

[JeffM]

I fail to see how you get 25/4 -1/4 from also I dont see how anything has been proven, all I see is some fancy rewriting. A bit more on the how and why so I can understand and solve other problems and not just the solution to this problem.

Also why don't write (k- 5/2)^2 >= 1/4 ?

To a certain extent, a proof by induction does LOOK like a bit of fancy rewriting.

Let's proceed with a bit more formality and try a different route.

\(\displaystyle 3^2 - 7(3) + 12 = 9 - 21 + 12 = -12 + 12 = 0.\) You did this step (but with a typographical error) in your first post.

Then you loosely expressed the second step (although n cannot be both k and k + 1).

\(\displaystyle k\ is\ an\ integer \ge 3\ such\ that\ k^2 - 7k + 12 = u \ge 0 \implies\)

\(\displaystyle (k + 1)^2 - 7(k + 1) + 12 = k^2 + 2k + 1 - 7k - 7 + 12 = (k^2 - 7k + 12) + 2k + 1 - 7 = u + 2k - 6 \ge 0 + 6 - 6 = 0.\)

\(\displaystyle THEREFORE\ n^2 - 7n + 12 \ge 0\ for\ every\ integer\ \ge 3.\)

We just rewrote \(\displaystyle (k + 1)^2 - 7(k + 1) + 12\) in terms of \(\displaystyle k^2 - 7k + 12\) plus some adjustments.

Then we show that the adjustments do not adversely affect what we assumed to be true of k.

The INTUITION is this.

If we show that something is true of some particular integer and also show that, if it is true for any specific integer, then it is also true for the next higher integer, the whole remaining row of dominoes falls. It is true of 3, so it is true for 4, but that means it is true for 5, which entails that it is true for 6, and so on world without end.

The easy part is almost always showing that it is true for some integer.

The tricky part is showing that if it is true for some arbitrary integer it is also true for the next integer. That part of the proof almost always comes down to expressing the property of interest for the next integer in terms of the arbitrary integer.

Does this help or make things worse?

 

[mmm4444bot]

I fail to see how you get 25/4 -1/4 from also I dont see how anything has been proven

From also?

The expression 25/4 - 1/4 results from a common process in algebra known as Completing the Square.

Of course you do not "see" any proof; Halls did not finish a proof. He clearly stated, "you just need to finish it". In other words, he intentionally left it unfinished so that you would have something to consider.

You may be confused with his approach because you have forgotten how to complete the square.

Also why don't write (k- 5/2)^2 >= 1/4 ?

Because that would be "begging the question". :cool:

 

[mmm4444bot]

JeffM's approach is what we find in most texts (although they do not generally introduce extra symbols).

You showed that k^2 - 7k + 12 is non-negative when k is 3.

You showed that increasing k by 1 causes k^2 - 7k + 12 to become k^2 - 5k + 6.

Jeff showed how k^2 - 5k + 6 can be written in terms of k^2 - 7k + 12:

k^2 - 5k + 6 is the same as (k^2 - 7k + 12) + 2k-6.

Well, we already know the first possible value for k^2 - 7k + 12; it's 0.

And, we know that the result of 0 + 2k - 6 will always be non-negative (because k cannot be less than 3). This proves that replacing k with k+1 results in a value greater than zero for all k.

I'm thinking that you would benefit from seeking-out and studying additional examples of proof by induction. There are a gazillion lessons and examples to be found via googling. :cool:

 

[diggsy]

To a certain extent, a proof by induction does LOOK like a bit of fancy rewriting.

Let's proceed with a bit more formality and try a different route.

\(\displaystyle 3^2 - 7(3) + 12 = 9 - 21 + 12 = -12 + 12 = 0.\) You did this step (but with a typographical error) in your first post.

Then you loosely expressed the second step (although n cannot be both k and k + 1).

\(\displaystyle k\ is\ an\ integer \ge 3\ such\ that\ k^2 - 7k + 12 = u \ge 0 \implies\)

\(\displaystyle (k + 1)^2 - 7(k + 1) + 12 = k^2 + 2k + 1 - 7k - 7 + 12 = (k^2 - 7k + 12) + 2k + 1 - 7 = u + 2k - 6 \ge 0 + 6 - 6 = 0.\)

\(\displaystyle THEREFORE\ n^2 - 7n + 12 \ge 0\ for\ every\ integer\ \ge 3.\)

We just rewrote \(\displaystyle (k + 1)^2 - 7(k + 1) + 12\) in terms of \(\displaystyle k^2 - 7k + 12\) plus some adjustments.

Then we show that the adjustments do not adversely affect what we assumed to be true of k.

The INTUITION is this.

If we show that something is true of some particular integer and also show that, if it is true for any specific integer, then it is also true for the next higher integer, the whole remaining row of dominoes falls. It is true of 3, so it is true for 4, but that means it is true for 5, which entails that it is true for 6, and so on world without end.

The easy part is almost always showing that it is true for some integer.

The tricky part is showing that if it is true for some arbitrary integer it is also true for the next integer. That part of the proof almost always comes down to expressing the property of interest for the next integer in terms of the arbitrary integer.

Does this help or make things worse?

This does help. I'm starting to grasp how it proves it. I've understood the intuition part previously but didn't get exactly how you showed it. Thanks!.

 

[HallsofIvy]

I fail to see how you get 25/4 -1/4 from also I dont see how anything has been proven, all I see is some fancy rewriting. A bit more on the how and why so I can understand and solve other problems and not just the solution to this problem.

Also why don't write (k- 5/2)^2 >= 1/4 ?

It's hard to believe you don't know how to "complete the square". A "perfect square" is of the form \(\displaystyle (x- a)^2= x^2- 2ax+ a^2\). Compare \(\displaystyle x^2+ 2ax\) with \(\displaystyle k^2- 5k\) and you will see that we need "2a= 5" so that a= 5/2 and \(\displaystyle (5/2)^2= 25/4\) so that \(\displaystyle k^2- 5k+ 6= k^2- 5k+ 25/4- 25/4+ 6= (k^2- 5/2)^2- 25/4+ 6\). Of course, \(\displaystyle -25/4+ 6= -25/4+ 24/4= -1/4\) so we have \(\displaystyle k^2- 5k+ 6= (k- 5/2)^2- 1/4\).

Now the point is, if k>= 3, then k- 5/2>= 1/2 so that (k- 5/2)^2- 1/4>= 0.

 

[HallsofIvy]

I understand that the problem said to use induction- but that is not the easiest way to do this.

The problem was to show that, for \(\displaystyle n\ge 3\), \(\displaystyle n^2- 7n+ 12\ge 0\).

Completing the square, \(\displaystyle n^2- 7n+ 12= n^2- 7n+ \frac{49}{4}- \frac{49}{4}+ 12= \left(n- \frac{7}{2}\right)^2- \frac{49}{4}+ \frac{48}{4}\)
\(\displaystyle = \left(n- \frac{7}{2}\right)^2- \frac{1}{4}\)

If \(\displaystyle n\ge 3\) then \(\displaystyle n- \frac{7}{2}\ge -\frac{1}{2}\) so that \(\displaystyle \left(n- \frac{7}{2}\right)^2\ge \frac{1}{4}\) and then \(\displaystyle \left(n- \frac{7}{2}\right)^2- \frac{1}{4}\ge 0\)