RE: Fw: Recursive Function
- To: mathgroup at smc.vnet.net
- Subject: [mg35935] RE: [mg35886] Fw: [mg35874] Recursive Function
- From: Constantine <celster at cs.technion.ac.il>
- Date: Thu, 8 Aug 2002 06:06:26 -0400 (EDT)
- References: <000e01c23d1c$f7cd9820$a1284484@cs.technion.ac.il>
- Sender: owner-wri-mathgroup at wolfram.com
I'm appreciated...
But.. when I try to solve (exactly as suggested):
In[16]:= SolveAlways[{t[n]==t[n-1]+s[n,2], t[2] == 0}, n]
I get:
SolveAlways::dinv:
The expression Which[n < 2, 0, 2 < 0, <<1>>, True,
Which[-1 + n < 2, <<5>>] + <<1>>] involves unknowns in more than one
argument, so inverse functions cannot be used.
2 3
Out[16]= SolveAlways[{a + b n + c n + d n ==
2 3
> a + b (-1 + n) + c (-1 + n) + d (-1 + n) +
> Which[n < 2, 0, 2 < 0, 0, True, s[n - 1, 2] + s[n, 2 - 1]],
> a + 2 b + 4 c + 8 d == 0}, n]
Thank you a lot for the given help.
Constantine Elster.
At 05:20 PM 8/6/2002 -0500, DrBob wrote:
>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
>Sent: Tuesday, August 06, 2002 2:44 AM
>Cc: drbob at bigfoot.com
>Subject: [mg35935] 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>majort at cox-internet.com>
To: mathgroup at smc.vnet.net
>
><<mailto:celster at cs.technion.ac.il>celster at cs.technion.ac.il>;
><<mailto:mathgroup at smc.vnet.net>mathgroup at smc.vnet.net>
>
>Sent: Monday, August 05, 2002 4:56 PM
>
>Subject: [mg35935] 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
> > Subject: [mg35935] [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>majort at cox-internet.com>
To: mathgroup at smc.vnet.net
> > Subject: [mg35935] [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
> > > Sent: Sunday, August 04, 2002 5:01 AM
> > > Subject: [mg35935] [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
> > >
> > >
> > >
> > >
> >
> >
> >
> >
Constantine Elster
Computer Science Dept.
Technion I.I.T.
Office: Taub 411
Tel: +972 4 8294375