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

```

• Prev by Date: Leibniz for Windows beta now available
• Next by Date: beep after calculation for Ver 3
• Previous by thread: Re: Problems with RSolve...
• Next by thread: output of 2d fortran arrays for post-processing (Q:)