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