Math Is Fun Forum

BlitzBall

Member

Registered: 2012-01-07

Posts: 92

Inductive step help! Again

Hi guys, I'm back, it has been a while.

Look at this answer:
Question: (2×1)+(2×2)+(2×3)+· · ·+(2×(n−1))+(2×n) = n×(n+1)

Base Case: n=1

Inductive step: (2 × 1) + (2 × 2) + (2 × 3) + · · · + (2 × k) + (2 × (k+1)) = (k + 1) × (k + 2)

L.H.S: (2 × 1) + (2 × 2) + · · · + (2 × k) + (2 × (k+1))
= k × (k + 1) + (2 × (k+1)) (by hypothesis)
= (k + 1) × (k + 2)
= R.H.S.

My question is how you get  k × (k + 1) + (2 × (k+1))    to     (k + 1) × (k + 2)? 

Is it something to do with simplifying or finding the common term?
Thanks.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Inductive step help! Again

Hi BlitzBall;

After you have done your base case of 1 you conjecture:

If that is true then

You already believe from step 2 that

So you can substitute it into step 3 (the boxed part).

Start simplifying by algebra.

What you know now is that step 2 implies step 3. That the kth term implies the k+1 term. You already no k=1 is true, so k = 2 is true. The k = 2 implies k = 3 etcetera. Proof by induction.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

BlitzBall

Member

Registered: 2012-01-07

Posts: 92

Re: Inductive step help! Again

Hi BlitzBall;

After you have done your base case of 1 you conjecture:

If that is true then

You already believe from step 2 that

So you can substitute it into step 3 (the boxed part).

Start simplifying by algebra.

What you know now is that step 2 implies step 3. That the kth term implies the k+1 term. You already no k=1 is true, so k = 2 is true. The k = 2 implies k = 3 etcetera. Proof by induction.

Ahh I get it now! By the way, do we have to simplify Right Hand Side: (k+1)(k+2) near the end?

Also, in the Inductive hypothesis: On the left hand side, there was (2 × (k−1)).  During the Inductive step where we add k+1 to n. I had something like this ... (2 × (K+1)-1). If i expanded that at the start of inductive step, do I only expand the right hand side of (2 × (K+1)-1) to get (2 × k)?

Thanks

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Inductive step help! Again

Hi;

Ahh I get it now! By the way, do we have to simplify Right Hand Side: (k+1)(k+2) near the end?

You only do as much until it becomes clear that you have an identity.

Your bracketing is wrong on the next part of your question. If you substitute k+1 for k in (2 × (k−1)) you would get

(2 × (k−1)) ->(2 × (k+1−1)) = 2k

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

BlitzBall

Member

Registered: 2012-01-07

Posts: 92

Re: Inductive step help! Again

Hi;

Ahh I get it now! By the way, do we have to simplify Right Hand Side: (k+1)(k+2) near the end?

You only do as much until it becomes clear that you have an identity.

Your bracketing is wrong on the next part of your question. If you substitute k+1 for k in (2 × (k−1)) you would get

(2 × (k−1)) ->(2 × (k+1−1)) = 2k

hmm, then where does the (2×k) come from in the inductive step?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Inductive step help! Again

Hi;

It is given to you in step 2). It is part of what you call the hypothesis.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

BlitzBall

Member

Registered: 2012-01-07

Posts: 92

Re: Inductive step help! Again

Hi;

It is given to you in step 2). It is part of what you call the hypothesis.

Ahh i see.

I'm still a little puzzled..

In the inductive hypothesis: (2 × 1) + (2 × 2) + (2 × 3) + · · · + (2 × (k−1)) + (2 × k) = k × (k + 1)

Up to the point where I include n=k+1 in inductive step, I would get something like this:

(2 × 1) + (2 × 2) + (2 × 3) + · · · + (2 × (k+1−1)) + (2 × k+1) = (k+1) × (k+2)

but the actual answer to the inductive step is..
(2 × 1) + (2 × 2) + (2 × 3) + · · · + (2 × k) + (2 × (k+1)) = (k + 1) × (k + 2)

I think it something wrong with my allocation of k+1. Its something you mentioned about the bracketing earlier.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Inductive step help! Again

Yes, it is a bracketing problem.

If you have 2k and you substitute k+1 for k you would not get (2 x k + 1)
You would get 2(k+1).

Also, you probably do not know this but that particular problem you have is what ignited the "Battle of Brooklyn."

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

BlitzBall

Member

Registered: 2012-01-07

Posts: 92

Re: Inductive step help! Again

Yes, it is a bracketing problem.

If you have 2k and you substitute k+1 for k you would not get (2 x k + 1)
You would get 2(k+1).

Also, you probably do not know this but that particular problem you have is what ignited the "Battle of Brooklyn."

Battle of Brooklyn, Very interesting lol. Didn't think that would ever end up in a war.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Inductive step help! Again

It did not. The "Battle for Brooklyn" as it is sometimes called ended quickly
with a complete victory for the bad guys.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

BlitzBall

Member

Registered: 2012-01-07

Posts: 92

Re: Inductive step help! Again

Ahh i see. Thanks for your help btw

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Inductive step help! Again

Hi BlitzBall;

Your welcome and good to see you.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

BlitzBall

Member

Registered: 2012-01-07

Posts: 92

Re: Inductive step help! Again

Hi, I was wondering, do you know how to do prove Time Complexity with Mathematical Induction? It's quite similar to math induction.

Last edited by BlitzBall (2012-05-25 07:13:42)

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: Inductive step help! Again

Could you post a specific question that is bothering you,so we can show you on that example.

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Inductive step help! Again

Hi BlitzBall;

No I do not. Got an example that I can see?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

BlitzBall

Member

Registered: 2012-01-07

Posts: 92

Re: Inductive step help! Again

T(n) = {1     n=1
          {T(n/2)+1   Otherwise

Guess: T(n) =< 2 log n
- Assume true for all n' < n [assume T(n/2) =< 2 x log (n/2)]

T(n) =T(n/2) + 1
       =<2 x log(n/2) + 1    <---by hypothesis
       =2x(log n – 1) + 1   <--- log(n/2) = log n – log 2
       <2log n

I think it's easier to understand without the T(n).
Also, what is n'? Is it primed?

Last edited by BlitzBall (2012-05-25 07:36:54)

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

Re: Inductive step help! Again

Assuming that n'<n means only that you assume it for all naturals less than n.The rest is basic induction.

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

BlitzBall

Member

Registered: 2012-01-07

Posts: 92

Re: Inductive step help! Again

Assuming that n'<n means only that you assume it for all naturals less than n.The rest is basic induction.

ahhh you are right. Maybe its best not to thing too much about T(n).