14,447,082 members
Rate this:
See more:
olve the following recurrences by obtaining a θ bound for T(N) given that T(1) = θ(1):
T(N) = N + T(N-3)

I've done the solving i just can't find the pattern.

step 0) N+ T(N-3)
step 1) 2N-3+T(N-6)
step2) 3N -9+T(N-9)
step3) 4N-18 +T(N-12)
step4) 5N-30 +T(N-15)
step) 6N-45+T(N-18) .... and so on. I have to find a pattern, an equation that works for every value for k.
Posted
Sergey Alexandrovich Kryukov 30-Jan-11 20:33pm

Is it a homework assignment problem? We're not interested to solve them. However, if you move in right direction and get stuck, you might hope for someone's help. Please...
--SA
Nithin Sundar 30-Jan-11 23:43pm

Do the math, form a logic and put it into your code. When you get stuck, show us what you have done and we'll guide you.
bowww 31-Jan-11 8:53am

I tried and I can't find a pattern that satisfies the second number 0,3,9,18,30,45... i Know it moves likes this ..3X1=3, adding 2 to the 1 ..3X3=9, adding 3 to the 3 gives you 3X6=18, adding 4 to the 6 gives u 3X10=30, adding 5 to the 10 3x15=45 ..my problem is that i cant find a general equation that satisfies all of the above.. i cant put it into an equation.
Sandeep Mewara 31-Jan-11 0:59am

I am not clear on what exactly you are looking for. You said you solved it and yet you seek a pattern. How come you solved without pattern. Surely I am missing something. Can you elaborate on what you are trying to do here and where are you stuck?
bowww 31-Jan-11 8:50am

ok I need to find a general equation that works for every value of k (0,1,2,3) and satisfies the pattern. as you can see the first Number increases by 1 the second number 1,3,9,18,30,45 is the part where i can't find an expression that satisfies it .. T(N-3),T(N-6),T(N-12)..increases by 3 each time.

Rate this:

## Solution 2

the second number 1,3,9,18,30,45 is the part where i can't find an expression that satisfies it
First of all, it's:
0, 3, 9, 18, 30, 45...

Now, the series is: Difference is increasing by amount 3...

Series: 0, 3, 9, 18, 30, 45...
Diff: 3(3-0), 6(9-3), 9(18-9), 12(30-18), 15(45-30)....

I guess, now, this should be enough for you, to get this series equation. :)

UPDATE:
Here you go, the link that will explain how I got that: same series that I told you[^]
v3
bowww 31-Jan-11 11:59am

I know it is 0,3,9,18.. i just mistyped the 1.. i still don't get what you are doing here, i tried understanding your method but cant seem to get it :S
Sandeep Mewara 31-Jan-11 12:00pm

It's 3,6,9,12,15... a simple AP series when you take the difference of 1st-2nd, 2nd-3rd, 3rd-4th, 4th-5th...
bowww 31-Jan-11 12:04pm

i get that it is the difference of 1st-2nd, 2nd-3rd, 3rd-4th, 4th-5th...but in order for me to make an equation for that I will only satisfy the first step .. im so confused.
Sandeep Mewara 31-Jan-11 12:08pm

It's basic class 12 maths.

Expression is: (3n + 3n^2)/2

You can get it yourself or you want me to explain how I got this?

bowww 31-Jan-11 12:06pm

my series is 0,3,9,18,30 ...so 3X0=0,3X1=3,3X3=9, 3x6=18 adding to the previosu value 1,2,3,4,5,6
Sandeep Mewara 31-Jan-11 12:18pm

bowww 31-Jan-11 12:37pm

i understand it but I can never know how to get those equations. I tried so many different ones but never got to this one. If you could explain that would be great:) thanks a lot for your help
Sandeep Mewara 31-Jan-11 12:38pm

The link I shared has exaclty the steps I take/took. Have a look at that and you too can try then.
bowww 31-Jan-11 12:39pm

ok thanks :) I really appreciate your help :)
Sandeep Mewara 31-Jan-11 12:41pm

My pleasure!
Sandeep Mewara 1-Feb-11 0:53am

Close the question that would help others too in future for something same.