Induction question

[Irwin Williams]

Hey team,

I'm stuck with this induction proof:

So, far, given: 

T(1) = 2
T(n)= 2T(n/2)+2
= 2(2T(n/[2^2])+2) + 2
= [2^2]T(n/[2^2]) + [2^2] + 2
= [2^2](2T(n/[2^2])+2) + [2^2] + 2
= [2^3]T(n/[2^3]) + [2^3] + [2^2] + 2  
= [2^3]T(n/[2^3]) + [2^3] + [2^2] + 1 + 1
.
.
.
= [2^k]T(n/[2^k]) + 2^k - 1 + 1

= [2^k]T(n/[2^k]) + 2^k 

How then do I show this to be correct (the proof).

So far I have:

Let (n/[2^k]) = 1

=> n = 2^k

So, T(n) = nT(1) + n

Thus, T(n) = 2n.

Proof (by induction):

When n = 1, T(1) = 2.

Assume T(k) is true, yielding: T(n) = 2n

//THIS IS WHERE I'M STUCK

--
Irwin Williams
785-1268
________________________
*I am a software solutions developer.*
Do you see a man skilled in his work?
He will serve before kings; he will not
serve before obscure men.
Proverbs 22:29

[Kyle E. deFreitas]

Unfortunately I am also stuck there

help anyone?

--
Kyle deFreitas
St Vincent and the Grenadines
Contact #: 1-784-454-4037
or
1-868-722-5346

[Irwin Williams]

but you're stuck at the same place?

So we've been going down the same correct road?

[Kyle E. deFreitas]

Not exactly the same road

but stuck at the same place

the difference

is in the summation

at ** the series must start from 0 

to apply the result

T(1) = 2

T(n)= 2T(n/2)+2

= 2(2T(n/[2^2])+2) + 2

= [2^2]T(n/[2^2]) + [2^2] + 2

= [2^2](2T(n/[2^2])+2) + [2^2] + 2

= [2^3]T(n/[2^3]) + [2^3] + [2^2] + [2^1]

= [2^k]T(n/[2^k]) + 2^k + .. . + 2^2 + 2^1

= [2^k]T(n/[2^k]) + 2[2^k-1 + .. . + 2^1 + 2^0]  **

= [2^k]T(n/[2^k]) + 2[2^K - 1]

Let (n/[2^k]) = 1

=> n = 2^k

= T(n) = nT(1) + 2(n -1)

= T(n) = 2n + 2n - 2

= T(n) = 4n -2

but I having difficulty with the iductive step of the proof

regards

[Irwin Williams]

What do you think of the answer provided here:

http://math.stackexchange.com/questions/9731/prove-by-induction-tn-2tn-2-2

[Kyle E. deFreitas]

I think that proposed solution makes no sense to the problem

we are trying to show the relationship between

as we assumed that 

2T(k/2) + 2 = 4(k) - 2

we need to show that

2T(k+1/2) + 2 = 4(k+1) -2

but then i not that strong in math...so who am i to say, but his proposal sheds no light on the problem for me

[Vincent Ramdhanie]

I just posted a reply. I have no idea how much sense it makes though.

http://math.stackexchange.com/questions/9731/prove-by-induction-tn-2tn-2-2/9743#9743

[Irwin Williams]

Vince, check this:

We know that T(1) = 2. We are trying to prove that T(n) = 4n-2.

This is trivially true for n = 1:

T(1) = 4(1) - 2
     = 4 - 2
     = 2

Assume

T(k) = 4k - 2

(FROM HERE, is where i diverge)

From the original definition:

T(k+1) = 2T( [k+1] / 2 ) + 2

//since we assumed up to T(k) is correct and (k+1)/2 is less than T(k), we substitute:

So, We have 2( 4( (k+1) /2) - 2  ) + 2

= 4(k+1)- 4 + 2

= 4(k+1) - 2

//Proven, since this answer is of the form we're looking for.

[Kyle E. deFreitas]

Das actually a really good solution

lol

[Vincent Ramdhanie]

cool

[Irwin Williams]

Vince, could you reply and update your answer so I can mark it accepted?

[vramd...@gmail.com]

Will do. Give me about 30 mins.

Sent from my BlackBerry® wireless device available from bmobile.

---

From: Irwin Williams <irwin.w...@gmail.com>

Sender: design-and-analy...@googlegroups.com

Date: Wed, 10 Nov 2010 14:14:40 -0400

To: <design-and-analy...@googlegroups.com>

ReplyTo: design-and-analy...@googlegroups.com

Subject: Re: Induction question

[Vincent Ramdhanie]

Irwin,

I updated the answer with your modifications.

Thanks

Vincent