       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:= eqn = t[2*n] == -1 + n + 2 t[n];

We rewrite this:

In:= eqn2 =  eqn /. n->2^k;

In:= eqn3 = eqn2 /. t[2^m_] -> s[m]
k
Out= s[1 + k] == -1 + 2  + 2 s[k]

In:= <<DiscreteMath`RSolve`

Say we have the first term in the sequence set to 1. We call RSolve with
eqn3 and this initial condition.

In:=  soln = First[RSolve[{eqn3, s==1}, s[k], k]]

-1 + k
Out= {s[k] -> 1 + 2       k}

In:= tsoln = Simplify[(soln /. s[j_]->t[2^j]) /. k->Log[2,n]]
n Log[n]
Out= {t[n] -> 1 + --------}
Log

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:)