Thread: 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

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


We need to show that the theorem is true for the next value of k, n + 1. That is, we need to show that:


Break down the sum on the LHS:


The sum in parenthesis is just , according to our assumption. So we have:

which is an identity, so the theorem is true for k = 1, thus k = 2, 3, 4, ...

-Dan

Thanks for the detailed explanation but I dont get this part

We need to show that the theorem is true for the next value of k, n + 1. That is, we need to show that:

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)?

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:


-Dan

Thank you for your help.

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.

Originally Posted by ff4930

Thank you for your help.

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


That

(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

and add 1 to both sides:

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

Now, note that


and because we also know that

So


Thus


(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

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.

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...

-Dan