Mathematical Induction help

• Aug 4th 2007, 11:55 AM
ff4930
Mathematical Induction help
Hi all, Im new to the forum and I am having difficulties understanding Inductions.

I have these 2 examples from the textbook and they give me answers but I was wondering if anyone can help me through it. I keep staring at it and it just doesn't sink in.

1st problem:
Prove that the sum of the first N odd positive integers = n^2

I get the first step prove that P(1) = true which is sum of the first odd integer which is 1 and 1^2 = 1.

The textbook puts 1+3+5+...+(2k-1)=k^2
I know 2k-1 ='s an odd integer but this is what confuses me

the textbook has 1+3+5....+(2k-1)+(2k+1) = (k+1)^2
then..
has 1+3+5....+(2k-1)+(2k+1) = [1+3+...(2k-1)] + (2k+1)
=k^2 + (2k+1) ---where did k^2 come from?
=k^2 + 2k + 1
=(k+1)^2
• Aug 4th 2007, 12:02 PM
topsquark
Quote:

Originally Posted by ff4930
Hi all, Im new to the forum and I am having difficulties understanding Inductions.

I have these 2 examples from the textbook and they give me answers but I was wondering if anyone can help me through it. I keep staring at it and it just doesn't sink in.

1st problem:
Prove that the sum of the first N odd positive integers = n^2

I get the first step prove that P(1) = true which is sum of the first odd integer which is 1 and 1^2 = 1.

The textbook puts 1+3+5+...+(2k-1)=k^2
I know 2k-1 ='s an odd integer but this is what confuses me

the textbook has 1+3+5....+(2k-1)+(2k+1) = (k+1)^2
then..
has 1+3+5....+(2k-1)+(2k+1) = [1+3+...(2k-1)] + (2k+1)
=k^2 + (2k+1) ---where did k^2 come from?
=k^2 + 2k + 1
=(k+1)^2

Typically in a mathematical induction problem you prove the statement for some specific value of k, then use the theorem itself to simplify your problem.

Specifically in your case we know that the theorem is true for k = 1.

Let me change your variables a bit. (This may make this more transparent, or it may confuse you. I hope the former!) Assume the theorem is true for some k = n. Then
$1 + 3 + ~ ... ~ + (2n - 1) = n^2$

We need to show that the theorem is true for the next value of k, n + 1. That is, we need to show that:
$1 + 3 + ~ ... ~ + (2n - 1) + (2n + 1) = (n + 1)^2$

Break down the sum on the LHS:
$(1 + 3 + ~ ... ~ + (2n - 1)) + (2n + 1) = (n + 1)^2$

The sum in parenthesis is just $n^2$, according to our assumption. So we have:
$n^2 + (2n + 1) = (n + 1)^2$
which is an identity, so the theorem is true for k = 1, thus k = 2, 3, 4, ...

-Dan
• Aug 4th 2007, 12:09 PM
ff4930
Thanks for the detailed explanation but I dont get this part

Quote:

We need to show that the theorem is true for the next value of k, n + 1. That is, we need to show that:
http://www.mathhelpforum.com/math-he...01a91cc4-1.gif
why is it 2n+1?
wouldn't next value be another odd integer which is (2n-1), and since is k+1 wouldn't it be (2n-1)+1? sorry if Im not seeing it right away.

Ok, is this right?
because they give us the formula for the next odd integer is 2 times(n-1)
so to find n+1 it is 2 times(n+1)?
• Aug 4th 2007, 02:05 PM
topsquark
Quote:

Originally Posted by ff4930
Thanks for the detailed explanation but I dont get this part

why is it 2n+1?
wouldn't next value be another odd integer which is (2n-1), and since is k+1 wouldn't it be (2n-1)+1? sorry if Im not seeing it right away.

Ok, is this right?
because they give us the formula for the next odd integer is 2 times(n-1)
so to find n+1 it is 2 times(n+1)?

The formula for the "k"th odd integer is 2k - 1. So the next one will be:
$2(k + 1) - 1 = 2k + 2 - 1 = 2k + 1$

-Dan
• Aug 4th 2007, 03:59 PM
ff4930

Ive tried applying what Ive learned from that to the 2nd example and if you can help clarify it because Im a little stuck.

prove n < 2^n
for all positive integers n

always have to prove the base step which is easy P(1) = 1 < 2^1 = 2

Then I have to prove that it is also correct for k+1 integers
which is to prove K + 1 < 2 ^k+1

Here is where Im stuck, the textbook says add 1 to both sides of k < 2^k, noting that 1 <= 2^k
which is k+1 < 2^k +1 <= 2^k + 2^k = 2^k+1

I just dont understand where the 2^k + 2^k came from.
• Aug 4th 2007, 04:10 PM
topsquark
Quote:

Originally Posted by ff4930

Ive tried applying what Ive learned from that to the 2nd example and if you can help clarify it because Im a little stuck.

prove n < 2^n
for all positive integers n

always have to prove the base step which is easy P(1) = 1 < 2^1 = 2

Then I have to prove that it is also correct for k+1 integers
which is to prove K + 1 < 2 ^k+1

Here is where Im stuck, the textbook says add 1 to both sides of k < 2^k, noting that 1 <= 2^k
which is k+1 < 2^k +1 <= 2^k + 2^k = 2^k+1

I just dont understand where the 2^k + 2^k came from.

One thing that is definitely confusing you is your notation. PLEASE USE PARENTHESIS!!!
You need to show that if
$n < 2^n$

That
$n + 1 < 2^{n + 1}$
(If you can't use the fancy LaTeX, write this as "n + 1 < 2^(n + 1)")

So let's take the hint. Let's look at
$n < 2^n$
and add 1 to both sides:

$n + 1 < 2^n + 1$ <-- "2^n + 1" is NOT "2^(n + 1)" This was an error in your work, I think. :confused:

Now, note that
$2^{n + 1} = 2^n \cdot 2 = 2^n + 2^n$

and because $1 \leq n$ we also know that $1 < 2 \leq 2^n$

So
$n + 1 < 2^n + 1 < 2^n + 2^n = 2^{n + 1}$

Thus
$n + 1 < 2^{n + 1}$

(Note: There may be an easier way to do this. This method was the first one that came to me after looking at the hint.)

-Dan
• Aug 4th 2007, 04:28 PM
ff4930
Thank You very much for taking time out to explain it.
My problem is grasping the information. Im going to die when the exam comes if Im having so much trouble with examples. Hopefully after some practice problems Ill be allright. Thanks again.
• Aug 4th 2007, 04:33 PM
topsquark
Quote:

Originally Posted by ff4930
Thank You very much for taking time out to explain it.
My problem is grasping the information. Im going to die when the exam comes if Im having so much trouble with examples. Hopefully after some practice problems Ill be allright. Thanks again.

Worry makes its own problems. Just find as many problems to work as you can and you'll get it down. Practice, practice, practice... :rolleyes:

-Dan