1. ## non-homogneous recurrence relation

Hi,

i like to solve the attached recurrence relation, i know the homogenous solution but the problem is with the cos term.

Help is appreciated!

Mopen

2. ## Re: non-homogneous recurrence relation

The cosine is periodic so you should only need consider four cases, yes?

What are the base cases?

3. ## Re: non-homogneous recurrence relation

sorry, what you mean by base cases?

4. ## Re: non-homogneous recurrence relation

I may be coming from a different field, but when we do recurrences in computer science, there needs to be some foundation from which the recurrence begins. It's important to consider the foundation in the event its contribution outweighs the rest of the recurrence.

For example, if T(n) = 3T(n/2) + n, you need to know what T(c) contributes for some small constant value (usually just described as T(0) since the value is irrelevant).

5. ## Re: non-homogneous recurrence relation

yes the recurrence starts from T(0)

6. ## Re: non-homogneous recurrence relation

Okay. Well, then you should be able to expand out the recurrence until it's completely periodic...maybe...

$T(n) = 2T(n-1) - T(n-2) - (2cos(n\pi/2))/(n-1)$
$T(n-1) = 2T(n-2) - T(n-3) - (2cos((n-1)\pi/2))/(n-2)$
$T(n-2) = 2T(n-3) - T(n-4) - (2cos((n-2)\pi/2))/(n-3)$
$T(n-3) = 2T(n-4) - T(n-5) - (2cos((n-3)\pi/2))/(n-4)$

So:

$T(n) = 4T(n-2) - T(n-2) - 2T(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$

$= 3T(n-2) - 2T(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$

$= 6T(n-3) - 3T(n-4) - (6cos((n-2)\pi/2))/(n-3) - 2T(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$

$= 4T(n-3) - 3T(n-4) - (6cos((n-2)\pi/2))/(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$

$= 8T(n-4) - 4T(n-5) - (8cos((n-3)\pi/2))/(n-4) - 3T(n-4) - (6cos((n-2)\pi/2))/(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$

$= 5T(n-4) - 4T(n-5) - (8cos((n-3)\pi/2))/(n-4) - (6cos((n-2)\pi/2))/(n-3) - (4cos((n-1)\pi/2))/(n-2) - (2cos(n\pi/2))/(n-1)$

Which confirms:

$T(n) = - (2cos(n\pi/2))/(n-1) - (4cos(n-1\pi/2))/(n-2) - (6cos(n-2\pi/2))/(n-2) - ...$

...over lg n many terms. We can reframe T(c) as T(1), after which the summation should be:

$T(n) = -2 \sum_{i=1}^{n} i(cos(n-i)\pi/2))/(n-i)$

EDIT: If we assume T(0) = 0 there's no problem but otherwise you have to add an extra 3^n * T(0) (roughly speaking) to the total for the contribution of the base case, but you didn't say what the base case contribution was. It appears to be substantial, however.

I'm not good at simplification of series with transcendentals (too applied for my tastes) but I assume you can handle it here.

Hope that helps!

7. ## Re: non-homogneous recurrence relation

Wait, I made a big error. Need to recalculate, give me a moment. I'll edit this message when finished.

EDIT: Nevermind, we're good. (For a moment there I thought I hadn't handled signs properly but I was always adding at the beginning of the recurrence so it works.)

EDIT 2: Although I did make an error with the cosines at the end...just fixed. I hope it's close to correct now. Either way you should see how I did it.

EDIT 3: Sheesh. Summation should go from 1 to n, and contribution of leaves is 3^n * T(0), which is significant unless T(0) = 0. Last fix, honest.

8. ## Re: non-homogneous recurrence relation

just small modification see the first attachement X is a variable 0<X<1 also i attached T(0) and T(1) as function of X

thank you so much

9. ## Re: non-homogneous recurrence relation

Oh! I thought that was 2 times, not 2x.

If there's an x and an n in there, I don't know what to make of it. I guess the x is a constant and you're looking for a result that hinges on both n and x, but that's frightening.

Recurrences in CS don't even get this crazy so it's beyond my ability to solve at present, and I don't have much interest in learning. Best of luck with it, maybe someone else can assist you.