More Recurrence Problems

[AlbaLed]

Solve the following recurrences:

1. T(1) = 1
   T(n) = 3T(n-1) + 2  for n>= 2

2. T(1) = 8
   T(n) = 3T(n-1) -15  for n>= 2

3. T(1) = 5
   T(n) = 2T(n-1) + 3n + 1  for n>= 2

4. T(1) = 1
   T(n) = 2T(n/2) + 6n - 1  for n = 2^k, k > 0

When you're done let me know and I'll put up more.
Have fun !!!!

AlbaLed

[jaideep]

1) 2.3^(n-1) - 1
2) 1/2*(3^(n-1) + 15)
3) 3n.2^(n-1) -1 - 6n + 6.2^(n-1)
4) 1 + (lg n)*6n

Nice one Alba. It was really a while since I last solved all these.
Keep pouring in.
Jaideep

[AlbaLed]

good job jaideep, almost all right
I think the answer to 3 is

(9 + 2n)*2^(n-1) - 3n - 3

I have not checke number 4, it is kinda late now, I'll pour more tomorrow

AlbaLed

[vik]

for those who forgot how to solve these, here is a nice explanation:
http://fmt.cs.utwente.nl/courses/adc/lec2.pdf (pages 35-45)

[AlbaLed]

Thanks for the link vik. That lecture has lots of useful info

Why not try to solve some of these

5. T(1) = 1
   T(n) = 3T(n/2) +n^2 - n  for n = 2^k, k > 0

6. T(1) = 1
   T(n) = T(n) + sqrt(n) + 1  for n = 4^k, k > 0

7. T(0) = 1
   T(1) = 6
   T(n) = T(n-2) +3n+4  for n >=3

8. T(1) = 1
   T(n) = nT(n-1) +n  for n >=2

Have fun !!!!

AlbaLed

[AlbaLed]

Any one working on these problems???

AlbaLed

[jaideep]

I gave up since they all looked similar. If they have anything special let us know and we can give that one a particular try.

Keep pouring in Alba.
Jaideep

[wood]

AlbaLed,

On 5) I got until: 3^K + n^2(1-(1/2)^K) - N(1 + 1/2 + ... 1/K)

I was trying to symplify it but got even worse! Something like:

3^K + n^2 - n - nloglog N + e (euler's constant for the harmonic series)

Let me know what I'm missing...

Wood

[wood]

Shouldn't (6) be

T(n) = T(n-1) + sqrt(n) + 1 ? ?


And what about (7),

T(2) is not defined?

[jaideep]

5) I got something like this

3^lgn + 4(1 - 3/4^lgn)*n^2 + 2n((3/2)^lgn - 1)

6) Yeah there is something missing in (6)

Jaideep