# Thread: More Recurrence Problems

1. Good post? |
Solve the following recurrences:
Code:
```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

2. Good post? |
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

3. Good post? |
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

4. Good post? |
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)

5. Good post? |
Thanks for the link vik. That lecture has lots of useful info

Why not try to solve some of these
Code:
```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

6. Good post? |
Any one working on these problems???

AlbaLed

7. Good post? |
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

8. Good post? |
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

9. Good post? |
Shouldn't (6) be

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

And what about (7),

T(2) is not defined?

10. Good post? |
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

Page 1 of 4 1234 Last

#### Thread Information

##### Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

SEO by vBSEO ©2010, Crawlability, Inc.