Struggling with the Inductive Step :(

BlitzBall · 2012-02-12 07:08:11

Hi guys, I'm back. The test was like 50/50 and have to wait for my results.

The problem i am having is math induction, I hate it!

The question is: 1+3+5+..+(2n-1) = n^2 for all positive integers n >= 1

When n=1.
Induction step when n=k+1, I get 1+3+5+...+2(k+1)-1 = (K+1)^2

Now, the next step is to prove it. But I have no idea how to prove 1+3+5+...+2(k+1)-1 = (K+1)^2 is true

Do I expand the left hand side 2(k+1)-1 and right hand side (K+1)^2 ???

Last edited by BlitzBall (2012-02-12 07:09:58)

bobbym · 2012-02-12 07:18:33

Hi BlitzBall;

math induction, I hate it!

When people say that they hate something it is meta-talk for I love it!

You proved it for the base case.

Assume that

is true.

So now you prove it for the next term k+1

Notice inside that series is your other series that you are assuming is true! You are assuming that it is equal to k^2. So you can substitute k^2 for what is in the box.

Expand the right.

Proved by induction!

BlitzBall · 2012-02-12 07:38:07

Hi,

The thing is how do you get K^2 for the left hand side??

Is it because of the Common Factors of both sides which is K ??

Last edited by BlitzBall (2012-02-12 07:38:49)

bobbym · 2012-02-12 07:40:26

Hi;

Do you understand that we assume this is true?

BlitzBall · 2012-02-12 07:43:12

Yep. Like n=k. Say you plot number 1 in both sides of k. And they are equally true. right??

bobbym · 2012-02-12 07:45:34

It is what we are trying to prove.

Now we try to prove that the next one is true.

The next series is

Cool up to here?

BlitzBall · 2012-02-12 07:48:51

Why is 2k-1 still exist up to that point? When you plot K+1, (2k-1) should be replaced by 2(k+1)-1.

bobbym · 2012-02-12 07:50:15

To extend your series you just add on the next term to the old series!

BlitzBall · 2012-02-12 07:52:31

Oh right. So when you plot K+1 on to (2k-1), you just add 2(k+1)-1 next to the formula??

bobbym · 2012-02-12 07:56:33

Yes, look at this little example;

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = something

the nth term is 9 and the next term ( n + 1 term ) is 10.

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = something else

See how the 9 which was the last term is now the second to last? It did not go away.

BlitzBall · 2012-02-12 07:59:14

Ahh I see. I get that now

bobbym · 2012-02-12 08:01:49

That is a horribly bad example mathematically but it does serve to get the point across.

If this is true

and this is true

and the base case is true then we are done. Do you agree up to here?

Do not forget to look at this page:

http://www.mathsisfun.com/algebra/mathe … ction.html

when we are done.

BlitzBall · 2012-02-12 08:05:55

Yup, because we're finding the proving that the next or any nth term is true.

bobbym · 2012-02-12 08:07:21

Notice inside that series is the first series that you are assuming is true!

You are assuming that it is equal to k^2. So you can substitute k^2 for what is in the box.

Expand the right.

Proved by induction!

BlitzBall · 2012-02-12 08:16:32

The funny thing is that my question is nearly the exact same as the link you posted lol! By the way with (2k-1) and 2(k+1), are we saying that (2k-1) is like the first term and 2(k+1) is the next?

bobbym · 2012-02-12 08:18:23

Not quite but you are getting close. 2k-1 is the next to the last term. The last term is 2(k+1)-1. Are you understanding what we have done so far?

BlitzBall · 2012-02-12 08:24:52

Ohh right i see. In general, do you think induction is hard??

anonimnystefy · 2012-02-12 08:28:19

hi BB

there's no in general when it comes to induction.it can range from extremely easy to extremely hard.

on of the mildly hard are the inductive proofs of the AM-GM inequality and Jensen's inequality.those are hard if you don't have any idea where to start and if you don't have any experience.

bobbym · 2012-02-12 08:30:48

Everything is hard when you do not know how. I do think it is hard. It is hard for me too.

One more point that will help you to understand it in an ordinary way.

What you have done is this:

If k is true then k + 1 is true. The next term is true. Now when you use the base case which you know is true now you can say k = 1 is true. So, k + 1 = 2 is true because it is the next term. Put 2 into k so that k = 2 and now you know that k + 1 = 3 is true because it is the next term. Put 3 into k so that k = 3 and now you know that k+1 = 4 is true because it is the next term. You can do that over and over until you cover all the numbers. Proof by induction!

BlitzBall · 2012-02-12 08:37:18

Oh right, yes i get that. Thanks for your help guys!

bobbym · 2012-02-12 08:42:57

Hi;

Have you ever introduced yourself in introductions?

anonimnystefy · 2012-02-12 08:43:24

also you need to beware of induction traps.Illustration:

Inductive proof that all horses are the same color.

1.The base case:
For one horse it is true because there is only one color,and this case is trivially true.

2.The inductive step:
Assume that every n horses are the same color.Let's proof that from this comes the fact that every n+1 horses are true:
Let's number the n+1 horses we are looking at with numbers 1 to n+1.If we take the horses numbered 1 to n,by the assumption we made we can say that those n horses are the same color.Now we take the horses 2 to n+1.There are n horses in there as well,so they are all the same color as well.And since horse 1 is the same color as horses 2 to n,and those are the same color as horse n+1,all n+1 horses are the same color.We have proved that from case for n horses we get that the theorem is true for n+1 horses,and we have also proved that the base case is true,so we have also proved the theorem.So,all horses are the same color.The end.

But wait.we can see that there is something wrong here.All horses are the same color.That's impossible.I have two horses of different colors in my garage.So BB can you figure out what's wrong with this proof?

BlitzBall · 2012-02-12 08:43:37

erm... nope.

bobbym · 2012-02-12 08:49:13

Hi Blitzball;

I was just wondering.

Math Is Fun Forum

#1 2012-02-12 07:08:11

Struggling with the Inductive Step :(

#2 2012-02-12 07:18:33

Re: Struggling with the Inductive Step :(

#3 2012-02-12 07:38:07

Re: Struggling with the Inductive Step :(

#4 2012-02-12 07:40:26

Re: Struggling with the Inductive Step :(

#5 2012-02-12 07:43:12

Re: Struggling with the Inductive Step :(

#6 2012-02-12 07:45:34

Re: Struggling with the Inductive Step :(

#7 2012-02-12 07:48:51

Re: Struggling with the Inductive Step :(

#8 2012-02-12 07:50:15

Re: Struggling with the Inductive Step :(

#9 2012-02-12 07:52:31

Re: Struggling with the Inductive Step :(

#10 2012-02-12 07:56:33

Re: Struggling with the Inductive Step :(

#11 2012-02-12 07:59:14

Re: Struggling with the Inductive Step :(

#12 2012-02-12 08:01:49

Re: Struggling with the Inductive Step :(

#13 2012-02-12 08:05:55

Re: Struggling with the Inductive Step :(

#14 2012-02-12 08:07:21

Re: Struggling with the Inductive Step :(

#15 2012-02-12 08:16:32

Re: Struggling with the Inductive Step :(

#16 2012-02-12 08:18:23

Re: Struggling with the Inductive Step :(

#17 2012-02-12 08:24:52

Re: Struggling with the Inductive Step :(

#18 2012-02-12 08:28:19

Re: Struggling with the Inductive Step :(

#19 2012-02-12 08:30:48

Re: Struggling with the Inductive Step :(

#20 2012-02-12 08:37:18

Re: Struggling with the Inductive Step :(

#21 2012-02-12 08:42:57

Re: Struggling with the Inductive Step :(

#22 2012-02-12 08:43:24

Re: Struggling with the Inductive Step :(

#23 2012-02-12 08:43:37

Re: Struggling with the Inductive Step :(

#24 2012-02-12 08:49:13

Re: Struggling with the Inductive Step :(

Board footer