2

This is my first question on this site... yesterday I asked this on cs.so but they downwote and told me that so.cs is a research-level site, not for students... I hope it's appropriate to ask this question here ...

I'm looking for a general way to solve recursions with non-equal exponents on left and right. for example: $$ \mathrm{T}(n^a)=c\mathrm{T}(n^b)+\mathrm{P}_d(n)\;\;\;\; a \neq b $$

for example:

$ T(n) = 4T(\sqrt{n})+1 , \;\; (n>2) $

$ T(2)=1, \;\; (n \leq 2) $

Community
  • 1
sorush-r
  • 133
  • Off-topic. Is there a particular reason why you use \mathrm in your LaTeX for T and P? I am just curious. :) – Srivatsan Oct 18 '11 at 14:03
  • So where should I get the answer or a start point, reference, etc? and no! there is no reason else than I don't like Italic things :-/ – sorush-r Oct 18 '11 at 14:36
  • What is $P_d$ ? – Phira Oct 18 '11 at 15:56
  • @Phira: a $d$-degree polynomial of $n$. – sorush-r Oct 18 '11 at 15:58
  • What kind of functions on which domain are you looking for? Do you have an example? Are the functions continuous? Or functions on the natural numbers ? Are there initial conditions?`Are you looking for asymptotics? – Phira Oct 18 '11 at 16:00
  • @Phira: What? $T(n)$ is $n$th term! isn't this obvious? – sorush-r Oct 18 '11 at 16:00
  • Oh! all terms are positive. they are in $\mathbb{N}$ and I'm trying to find the big-oh of recurrence. – sorush-r Oct 18 '11 at 16:02
  • @Sorush As indicated by the other comments, your question is poorly asked. I recommend reading other questions so you can see how to ask a good one. In particular you should explain what your symbols mean. Since many questions on math.stackexchange are also poorly worded, you might want to try MathOverflow (MO) instead. In particular, MO has a nice how to ask page. – Quinn Culver Oct 18 '11 at 16:12
  • @QuinnCulver. OK. Thank you for link :) – sorush-r Oct 18 '11 at 16:16
  • I think that the question is on-topic here even if it was originally formulated a bit unclearly. I don't know much general theory, but the structure of the example recurrence relation suggests first looking at the function $S(k):=T(2^{2^k})$. I collected this and another hint to an answer. So compute $S(0)=T(2)$, $S(1)=T(4)$, $S(2)=T(16)$ first, and see if you see a more familiar recurrence relation there. Ask, if you can't make any headway. – Jyrki Lahtonen Oct 18 '11 at 20:48
  • I'm sorry, but this is a student-level site, not for research. (just kidding) – Gerry Myerson Oct 19 '11 at 02:54

1 Answers1

2

Only answering the example.

Hint: What do you get, when you substitute $n=2^{2^k}$? Can you fill in the gaps? Try with small inputs $n=3,5,6,\ldots$ outside the set of values described in the first suggestion.

Jyrki Lahtonen
  • 133,153