RE: Fw: Recursive Function
- To: mathgroup at smc.vnet.net
- Subject: [mg35916] RE: [mg35886] Fw: [mg35874] Recursive Function
- From: "DrBob" <majort at cox-internet.com>
- Date: Thu, 8 Aug 2002 06:06:07 -0400 (EDT)
- Reply-to: <drbob at bigfoot.com>
- Sender: owner-wri-mathgroup at wolfram.com
First look at a small table to see how the powers of p and (1-p) go.
Then simplify the definition, leaving out p and (1-p), because it's easy
to deal with those:
ClearAll[s]
s[0, 0] = 1;
s[k_, m_] := Which[k < m, 0, m < 0, 0, True, s[k - 1, m] + s[k, m - 1]]
Look at the table again, and you'll see that the constants haven't
changed.
Next step, notice that
s[n_,1]:=n
and add that to the definition.
You can also notice that S[n_,2] grows like the sum of the first n
integers, but offset by one, so
s[n_, 2] := -1 + n*((n + 1)/2)
Add that to the definition too.
Next, define
ClearAll[t]
t[n_]:=a + b n + c n^2 + d n^3
and use SolveAlways to find a, b, c, and d so that
{t[n]==t[n-1]+s[n,2], t[2]==0}
That gives a formula for s[n,3]. Add that to the definition.
Define a new t[n_] with one more power of n and solve again, this time
the equations
{t[n]==t[n-1]+s[n,3], t[3]==0}
That gives s[n,4], and that's far enough with that. Now you factor each
s[n,k] for k=1 to 4 and look for a pattern. It's easy enough to figure
out, in terms of factorials.
The result has non-zero entries above the diagonal, but that's no
problem.
Now that you have the formula (you hope), you need to prove that it
satisfies the recurrence formula.
That's enough hints, I think.
Bobby
-----Original Message-----
From: Constantine Elster [mailto:celster at cs.Technion.AC.IL]
To: mathgroup at smc.vnet.net
Subject: [mg35916] Re: [mg35886] Fw: [mg35874] Recursive Function
Sorry, the function that I sent earlier was written with mistake.
It should be
S[0,0] = 1
S[k_,m_] := Which [
k < 0, 0,
m < 0, 0,
k < m, 0,
True, p*S[k-1,m] + (1-p)*S[k,m-1]]
Pls reply if you know a hint how to find the non recursive equivalent...
Thanks a lot in advance.
Constantine Elster.
Constantine Elster
Computer Science Dept.
Technion I.I.T.
Office: Taub 411
Tel: +972 4 8294375
----- Original Message -----
From: "DrBob" < <mailto:majort at cox-internet.com>
To: mathgroup at smc.vnet.net
majort at cox-internet.com>
celster at cs.technion.ac.il>; < <mailto:mathgroup at smc.vnet.net>
mathgroup at smc.vnet.net>
Subject: [mg35916] RE: [mg35886] Fw: [mg35874] Recursive Function
> If you look at the function a bit, it's not hard to figure out.
>
> s[0, 0] = 1
> s[k_, m_] := Which[k < 0, 0, m < 0, 0, True, p*s[k - 1, m] + q*s[k, m
-
> 1]]
> Table[s[n, m], {n, 0, 4}, {m, 0, 4}] // TableForm
>
> (output omitted)
>
> Look at the Table and you should notice that diagonals (lower left to
> upper right) are the terms of (p+q)^(n+m). Therefore, the general
> formula is
>
> Binomial[n+m,m] p^n q^m
>
> There's a more involved (and general) way of doing this, by defining a
> function f[p,q]=Sum[S[n,m],{n,0,Infinity},{m,0,Infinity}] and using
the
> recurrence relation to work out an equation involving f and then solve
> it for f. Once you know what f is, you find its series expansion, and
> that gives you your original S terms. In a roundabout way (for this
> example) you'd wind up making the same discovery that I mentioned
above,
> just from looking at the Table.
>
> Finally, you could use RSolve to get one row at a time of the Table
> above. Once you've done a few, you should see the pattern.
>
> Using any of those methods, it will be helpful to remember that the
> recurrence relation (and hence the Table) is symmetric (with a switch
of
> p and q). Hence, figuring out a row also gives you a column. That
> makes it natural, by the way, to look at the diagonals as I did above.
>
> Bobby Treat
>
> -----Original Message-----
> From: Constantine Elster [mailto:celster at cs.technion.ac.il]
To: mathgroup at smc.vnet.net
> Sent: Monday, August 05, 2002 5:02 AM
> To: <mailto:mathgroup at smc.vnet.net> mathgroup at smc.vnet.net
> Subject: [mg35916] [mg35886] Fw: [mg35874] Recursive Function
>
> Hi, all.
>
> In the help pages I found how to find a non recursive function
> equivalent to
> a function that has one argument.
> More precisly I'm looking for a general non-recursive formula for the
> following recursive function (has 2 arguments):
>
> S[0,0] = 1
> S[k_,m_] := Which [
> k < 0, 0,
> m < 0, 0,
> True, p*S[k-1,m] + (1-p)*S[k,m-1]]
>
> I'll be very pleasant if anyone can help or give a hint in how to find
> the
> equivalent non-recursive function.
> Thanks in advance.
> Constantine.
>
> Constantine Elster
> Computer Science Dept.
> Technion I.I.T.
> Office: Taub 411
> Tel: +972 4 8294375
>
>
> ----- Original Message -----
> From: "DrBob" < <mailto:majort at cox-internet.com>
To: mathgroup at smc.vnet.net
majort at cox-internet.com>
> To: <mailto:mathgroup at smc.vnet.net> mathgroup at smc.vnet.net
> Subject: [mg35916] [mg35886] RE: [mg35874] Recursive Function
>
>
> > >>Can Mathematica find a non-recursive function equivalent to a
given
> > recursive function?
> >
> > Sometimes. Look for "recurrence relations" in Help. In general, it
> > requires thought, and that's YOUR job, not Mathematica's. See below
> for
> > hints.
> >
> > Look up "Recursive functions" in help and read the section on
> functions
> > that remember their values. Note two important points, in addition
to
> > what it says there:
> >
> > 1) You're trading space for time. If the values you're saving take
> up
> > a LOT of space and/or you're saving a LOT of values, that can become
a
> > problem.
> >
> > 2) If you compute, for instance, F[2000] and F is recursive (with
or
> > without saving values) you'll run into $RecursionLimit. The simple
> fix
> > is to make sure you compute things from bottom up rather than top
> down.
> > If the first thing you need is F[2000], compute the others first
like
> > this:
> >
> > Last[F/@Range[2000]]
> >
> > You can also use a non-recursive definition like the following (for
> the
> > Fibonacci example). If you want the n-th term of the Fibonacci
> series,
> > do something like this:
> >
> > nxt[{a_, b_}] := {b, a + b}
> > fib[n_] := Last[Nest[nxt, {0, 1}, n - 1]]
> > fib[7]
> > fib /@ Range[10]
> >
> > 13
> > {1, 1, 2, 3, 5, 8, 13, 21, 34, 55}
> >
> > This method is best if you won't need again the values you've
already
> > computed; if you will, save values as explained in Help.
> >
> > Bobby Treat
> >
> > -----Original Message-----
> > From: Constantine [mailto:celster at cs.technion.ac.il]
To: mathgroup at smc.vnet.net
> To: <mailto:mathgroup at smc.vnet.net> mathgroup at smc.vnet.net
> > Sent: Sunday, August 04, 2002 5:01 AM
> > Subject: [mg35916] [mg35886] [mg35874] Recursive Function
> >
> > Hi,
> > Can Mathematica find a non-recursive function equivalent to a given
> > recursive function?
> > Anyone who knows, please, please, please, reply...
> >
> >
> > Constantine Elster
> > Computer Science Dept.
> > Technion I.I.T.
> > Office: Taub 411
> > Tel: +972 4 8294375
> >
> >
> >
> >
>
>
>
>