Re: Problems with RSolve...

*To*: mathgroup at smc.vnet.net*Subject*: [mg14581] Re: Problems with RSolve...*From*: Daniel Lichtblau <danl>*Date*: Fri, 30 Oct 1998 03:07:48 -0500*Organization*: Wolfram Research, Inc.*References*: <719fiq$ldb@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

matt wrote: > > I'm having problems with RSolve when applying it to the following type > of recurrence > relation: > > T(n) = 2 T(n/2) +n -1 > > (The type of relation you get when analyzing Merge-Sort). I can't seem > to get > Mathematica to give me an analytical solution. Does anyone have any > ideas as to why? > > thanks, > > matt > housemat at wam.umd.edu I do not think RSolve will handle this without a bit of massaging. Since your progression is geometric rather than sequential you might mess with a logarithmic substitution. Specifically, one might (i) Replace n by 2^k. (ii) Replace t[2^j] by s[j]. (iii) Solve a recurrence for s. (iv) Substitute back to get t[n]. In your particular example we begin with In[1]:= eqn = t[2*n] == -1 + n + 2 t[n]; We rewrite this: In[3]:= eqn2 = eqn /. n->2^k; In[4]:= eqn3 = eqn2 /. t[2^m_] -> s[m] k Out[4]= s[1 + k] == -1 + 2 + 2 s[k] In[5]:= <<DiscreteMath`RSolve` Say we have the first term in the sequence set to 1. We call RSolve with eqn3 and this initial condition. In[9]:= soln = First[RSolve[{eqn3, s[0]==1}, s[k], k]] -1 + k Out[9]= {s[k] -> 1 + 2 k} In[16]:= tsoln = Simplify[(soln /. s[j_]->t[2^j]) /. k->Log[2,n]] n Log[n] Out[16]= {t[n] -> 1 + --------} Log[4] You can infer from the gaps in the In[] sequence that this took a bit of tweaking. Daniel Lichtblau Wolfram Research