# Mathematical induction

• October 5th 2009, 12:33 PM
flexus
Mathematical induction
Use mathematical Induction to prove the formula for all integers n with the given values:

11+15+19...+(4n+7)=2n^2+9n , n≥1
• October 5th 2009, 12:52 PM
Matt Westwood
Quote:

Originally Posted by flexus
Use mathematical Induction to prove the formula for all integers n with the given values:

11+15+19...+(4n+7)=2n^2+9n , n≥1

When n=1 the expression is true. That's the basis of the induction.

Then you assume it's true for $n=k$, for some $k \ge 1$, and from that, you try and derive the truth of that expression for $n = k+1$.

So by assuming that $11+15+19...+(4k+7)=2k^2+9k$ is true (this is your induction hypothesis), you want to prove that:

$11+15+19...+(4(k+1)+7)=2(k+1)^2+9(k+1)$.

The way you would do that is to say that:

$11+15+19...+ (4k+7) + (4(k+1)+7) = 2k^2+9k + (4(k+1)+7)$

using the induction hypothesis.

Now you want to show that the RHS is $2(k+1)^2+9(k+1)$.

Match up what I've said above with what your text book says about proof by induction and try and work out the why of it rather than the what.
• October 5th 2009, 08:32 PM
flexus
so im trying to show that the formula 2(k+1)^2+9(k+1) is true??
• October 5th 2009, 09:30 PM
Matt Westwood
Do you actually understand how "mathematical induction" actually works?
• October 5th 2009, 09:34 PM
flexus
Quote:

Originally Posted by Matt Westwood
Do you actually understand how "mathematical induction" actually works?

im not gonna lie to you ...no im actually really trying to learn it because i caught the flu and missed class that day. there is an example in the book but it really does not help that's why i picked a question out of the book and trying to get anyone to work it out for me so i can see the pattern and use it as an example for my other problems. ....yea so these past couple post i must looked really dumb because i made no sense. im sorry.
• October 5th 2009, 10:35 PM
Matt Westwood
It works like this.

You've got a proposition involving n that you're trying to trying to prove is true for all n. (The usual example is $1+2+3+...+n = \frac {n(n+1)}2$).

First you show it's true for n=1 (or n=0, or whatever, depends on the expression). In the above case, we have $1 = \frac {1(1+1)}2$. This is called the "basis for the induction (or the "base case").

Then you say: "Suppose this proposition is true for $n=k$, where $k$ is any number $\ge 1$. Let's just, for a time being, assume that it's true." In the above example, we see that means $1+2+3+...+k = \frac {k(k+1)}2$. This is called the "induction hypothesis".

Now, if by assuming that it's true for $k$, we can prove it's true for $k+1$, we know that it will then be true for all $n$. This is called the "induction step".

In the above, we want to show that $1+2+3+...+k+(k+1)= \frac {(k+1)((k+1)+1)}2 = \frac {(k+1)(k+2)}2$.

And we do that by saying:

$1+2+3+...+k+(k+1)$

$= \frac {k(k+1)}2+(k+1)$ (we've used the induction hypothesis here, which we temporarily assumed true above)

$= \frac {(k+1)(k+2)}2$ (by some fairly straightforward algebra)

And so we have shown that:

IF $1+2+3+...+k = \frac {k(k+1)}2$ is true,

THEN $1+2+3+...+k+(k+1)= \frac {(k+1)(k+2)}2$ is true.

And we already know that it's true when k=1.

So, "by the principle of mathematical induction", or "by mathematical induction", or just "by induction", $1+2+3+...+n = \frac {n(n+1)}2$ is true for ALL values of n.

See how it works? Now see how I've applied the above to the question you asked.

It's true for 1. And, if it's true for $k$, then it's true for $k+1$.

Because it's true for 1, it's true for 1+1=2. And because it's true for 2, it's true for 2+1 = 3. And because it's true for 3, it's true for 3+1 = 4. And so on. Thus it's true for all numbers, by the fact that the numbers all go 1, 2, 3, 4, ... and so on "to infinity".

There are several underlying philosophical questions underlying the validity of the above. So much so, that the "principle of induction" is taken as an axiom (that is, a "postulate", or "basic truth") of the system of natural numbers. So don't take it too much to heart if you're not sure it "makes sense" or feel that the reasoning seems a little flimsy - the logical justification is a deep question.
• October 5th 2009, 11:18 PM
flexus
Quote:

Originally Posted by Matt Westwood
It works like this.

You've got a proposition involving n that you're trying to trying to prove is true for all n. (The usual example is $1+2+3+...+n = \frac {n(n+1)}2$).

First you show it's true for n=1 (or n=0, or whatever, depends on the expression). In the above case, we have $1 = \frac {1(1+1)}2$. This is called the "basis for the induction (or the "base case").

Then you say: "Suppose this proposition is true for $n=k$, where $k$ is any number $\ge 1$. Let's just, for a time being, assume that it's true." In the above example, we see that means $1+2+3+...+k = \frac {k(k+1)}2$. This is called the "induction hypothesis".

Now, if by assuming that it's true for $k$, we can prove it's true for $k+1$, we know that it will then be true for all $n$. This is called the "induction step".

In the above, we want to show that $1+2+3+...+k+(k+1)= \frac {(k+1)((k+1)+1)}2 = \frac {(k+1)(k+2)}2$.

And we do that by saying:

$1+2+3+...+k+(k+1)$

$= \frac {k(k+1)}2+(k+1)$ (we've used the induction hypothesis here, which we temporarily assumed true above)

$= \frac {(k+1)(k+2)}2$ (by some fairly straightforward algebra)

And so we have shown that:

IF $1+2+3+...+k = \frac {k(k+1)}2$ is true,

THEN $1+2+3+...+k+(k+1)= \frac {(k+1)(k+2)}2$ is true.

And we already know that it's true when k=1.

So, "by the principle of mathematical induction", or "by mathematical induction", or just "by induction", $1+2+3+...+n = \frac {n(n+1)}2$ is true for ALL values of n.

See how it works? Now see how I've applied the above to the question you asked.

It's true for 1. And, if it's true for $k$, then it's true for $k+1$.

Because it's true for 1, it's true for 1+1=2. And because it's true for 2, it's true for 2+1 = 3. And because it's true for 3, it's true for 3+1 = 4. And so on. Thus it's true for all numbers, by the fact that the numbers all go 1, 2, 3, 4, ... and so on "to infinity".

There are several underlying philosophical questions underlying the validity of the above. So much so, that the "principle of induction" is taken as an axiom (that is, a "postulate", or "basic truth") of the system of natural numbers. So don't take it too much to heart if you're not sure it "makes sense" or feel that the reasoning seems a little flimsy - the logical justification is a deep question.

thank you so much for the explanation. ok this is what i did. but now im stuck can you help me finish this.

so from your example n=1 so (4)(1)+7=2(1)^2+9(1) which = 11=11 so true

i assume that n=k , 11+15+19+...+(4K+7)=2K^2+9k is true

now i must prove for (k+1) 11 +15 +19+...+(4(k+1)+7)=2(k+1)^2+9(k+1)
11+15+19+...+(4(k+1)+7)=2(k^2+2k+1)+9k+1
11+15+19+...+(4(k+1)+7)=2k^2+13K+11
now i add the (4k+7) to both sides from the induction hypothesis
11+15+19+...+(4k+7+4(k+1)+7=2k^2+9k+(4(k+1)+7)

no this is where in stuck now.. what is next and how do i finish it. lol its like 3:18 am where in at. im dead tired.(Headbang)
• October 6th 2009, 04:58 AM
Quote:

Originally Posted by flexus
thank you so much for the explanation. ok this is what i did. but now im stuck can you help me finish this.

so from your example n=1 so (4)(1)+7=2(1)^2+9(1) which = 11=11 so true

i assume that n=k , 11+15+19+...+(4K+7)=2K^2+9k is true

now i must prove for (k+1) 11 +15 +19+...+(4(k+1)+7)=2(k+1)^2+9(k+1)
11+15+19+...+(4(k+1)+7)=2(k^2+2k+1)+9k+1
11+15+19+...+(4(k+1)+7)=2k^2+13K+11
now i add the (4k+7) to both sides from the induction hypothesis
11+15+19+...+(4k+7+4(k+1)+7=2k^2+9k+(4(k+1)+7)

no this is where in stuck now.. what is next and how do i finish it. lol its like 3:18 am where in at. im dead tired.(Headbang)

HI

When you need to prove that A = B , you must either start from A , then work it out to be B or vice versa .

$11 +15 +19+...+(4(k+1)+7)=2k^2+9k+(4(k+1)+7)$

11 +15 +19+...+(4k+7)+(4(k+1)+7)

=2k^2+9k+4k+4+7

$=2k^2+4k+2+9k+9$ and this will give you the desired result after simplifying

4k+7 is the terms before that .
• October 6th 2009, 06:44 AM
stapel
Quote:

Originally Posted by flexus
im not gonna lie to you ...no im actually really trying to learn [how to do induction proofs] because i caught the flu and missed class that day.

To make up for the class(es) you missed, try here. (Wink)