Hello,

I cannot solve the following problem:

What can we say about the asymptotic behavior, depending on the initial conditions, of a recurrence relation that has a inhomogeneous part (log n)^(log n) and has roots 1,2,3 ?

Printable View

- Oct 3rd 2010, 10:55 AMaa2010Recurrence relation
Hello,

I cannot solve the following problem:

What can we say about the asymptotic behavior, depending on the initial conditions, of a recurrence relation that has a inhomogeneous part (log n)^(log n) and has roots 1,2,3 ? - Mar 29th 2011, 10:44 PMbkarpuz
Hi

**aa2010**,

I am assuming that you are asking about the asymptotic nature of the difference equation

for

under the initial conditions

, and .

Here, is the forward difference operator, i.e., and .

For such problems, you need to compute the fundamental solutions, i.e.,

the solutions of the following initial value problems

: for with , and

: for with , and

: for with , and .

Then, by the variation of constants formula, we can write the solution as follows

for .

Here, we have

for

for

and

for .

Assume that , then for , which yields

.........

for all .

Thus, if (the coefficients of the dominant term ), then as .

Obtaining a complete result for your problem requires a deep inspection since the forcing term is not a nice one. (Itwasntme) - Mar 29th 2011, 11:24 PMbkarpuz
As I said, better inequalities will give you better results.

Note that for , we have ,

then the contribution of the forcing term to the solution can not be less than

for all .

As ,

,

which implies that yields as .