| Stan is still interested in this problem:
(The various USENET postings are separated by editorial comments
by me; these are marked at the left margin with a DVD, my initials.)
Newsgroups: sci.math
Path: decwrl!ucbvax!agate!ig!uwmcsd1!bbn!rochester!pt.cs.cmu.edu!andrew.cmu.edu!jk3k+
Subject: finder of lost sequences
Posted: 19 Apr 88 12:42:50 GMT
Organization: Carnegie Mellon University
This is a strange but serious advertisement: I analyze integer sequences.
Send me a recursion or sum to compute the sequence, and if all goes well i'll
send you a closed form. If you already know the answer, why ask?
--Joe
DVD: Stan's reply:
Newsgroups: sci.math
Path: decwrl!pyramid!ames!necntc!linus!alliant!stan
Subject: Re: finder of lost sequences
Posted: 21 Apr 88 19:11:09 GMT
Organization: Alliant Computer Systems, Littleton, MA
[email protected] (Joe Keane) writes:
>Send me a recursion or sum to compute the sequence, and if all goes well i'll
>send you a closed form.
I am interested in a closed form solution to the following recurrence:
p[1] = 1
p[2] = 2
p[n] = n p[n-1] + p[n-2]
(I have been working on this for a long time.)
Stanley Rabinowitz
Alliant Computer Systems Corporation
[email protected]
+1 (617) 486-1218
DVD: In .0, the initial conditions led to f(1) = 1, f(2) = 3.
In the above, Stan asked about p[1] = 1, p[2] = 2.
I liked the comment about "working on this for a long time."!
Now I'll skip the article that gave the formula for the
Fibonacci sequence, and go on to:
Newsgroups: sci.math
Path: decwrl!labrea!agate!cartan!brahms!desj
Subject: Re: finder of lost sequences
Posted: 23 Apr 88 00:29:38 GMT
Organization: UC Berkeley Math Dept
In article <[email protected]> [email protected] (Stanley Rabinowitz) writes:
>I am interested in a closed form solution to the following recurrence:
>
>p[1] = 1
>p[2] = 2
>p[n] = n p[n-1] + p[n-2]
>
>(I have been working on this for a long time.)
Define a(n,m,k) to be the sum of 1/(i1*(i1+1)*i2*(i2+1)*...*ik*(ik+1))
over all possible integer choices of m <= i1 < i1+1 < i2 < i2+1 < ... <
ik < ik+1 <= n.
There is a straightforward recursion for a:
a(n,m,k) = 1 if k=0,
sum(a(n,i+2,k-1)/(i*(i+1)), i, m, n-2*k+1) if k>0.
In fact, a has a closed form:
factorial(m-1) * binomial(n-k-m+1,k)
a(n,m,k) = ----------------------------------------------- .
factorial(k) * factorial(k+m-1) * binomial(n,k)
[We leave this as an exercise for the reader. :-) ]
Now, a little thought shows that there is a reason behind this
madness, namely that p is closely related to a. If you simply take the
recurrence relation on p[n] and expand the rhs over and over, you get a
bunch of terms which look suspiciously like terms in the definition of
a(n,1,k) for various values of k, multiplied by n!.
There is one little hitch, which is that the terms corresponding to
i1=1 in the definition of a do not contribute to p (they would
contribute if p[0] were taken to be 1 instead). Fortunately, for n>=2
we can subtract these terms off---they are just the terms in the
definition of a(n,3,k) for various values of k, multiplied by n!/2.
So,
p[n] = n! ( sum(a(n,k,1), k, 0, quotient(n,2)) -
sum(a(n,k,3)/2, k, 0, quotient(n,2)-1) )
n n
- - - 1
2 2
==== ====
\ binomial(n - k, k) \ binomial(n - k - 2, k)
= n! ( > ------------------ - > --------------------------)
/ 2 / k! (k + 2)! binomial(n, k)
==== k! binomial(n, k) ====
k = 0 k = 0
for n>=2. Finally, some values of p[n] courtesy of Macsyma:
(c5) [p(2),p(3),p(4),p(5),p(6),p(7),p(8),p(9),p(10),p(11),p(12),p(13),
p(14),p(15),p(16),p(17),p(18),p(19),p(20)];
(d5) [2, 7, 30, 157, 972, 6961, 56660, 516901, 5225670, 57999271, 701216922,
9173819257, 129134686520, 1946194117057, 31268240559432, 533506283627401,
9634381345852650, 183586751854827751, 3681369418442407670]
-- David desJardins
DVD: I haven't examined any of the replies, but from just skimming
it that one looks very good. The next, by the one who requested
"lost sequences," gives an asymptotic form:
Newsgroups: sci.math
Path: decwrl!labrea!agate!pasteur!ames!mailrus!tut.cis.ohio-state.edu!bloom-beacon!mit-eddie!bbn!rochester!pt.cs.cmu.edu!andrew.cmu.edu!jk3k+
Subject: Re: finder of lost sequences
Posted: 23 Apr 88 12:04:16 GMT
Organization: Carnegie Mellon
In-Reply-To: <[email protected]>
Just to let you know, someone else asked me this and i am working on it. It's
asymptotically C*n! (so it's not the Fibonacci sequence) where C is some
constant i know to many decimal places but that's it. If anyone knows the
answer, i'd like to hear it.
--Joe
DVD: I'll skip a "no, not the Fibonacci sequence"-type reply to the
one I skipped earlier, and move on to more asymptotic analysis:
Newsgroups: sci.math
Path: decwrl!ucbvax!pasteur!ames!lll-tis!lll-winken!uunet!mnetor!utzoo!utgpu!water!watmath!watdragon!ghgonnet
Subject: Re: finder of lost sequences
Posted: 23 Apr 88 14:02:38 GMT
Organization: U of Waterloo, Ontario
In article <[email protected]>, (Stanley Rabinowitz) writes:
>
> I am interested in a closed form solution to the following recurrence:
>
> p[1] = 1
> p[2] = 2
> p[n] = n p[n-1] + p[n-2]
>
I cannot give you a closed form solution, (I doubt one exists), but
usually asymptotic information is very helpful to clarify these problems.
Here is a bit of asymptotic analysis on the above:
|\^/|
._|\| |/|_. Watmum at Univ of Waterloo
\ MAPLE / Version 4.3 --- Feb 1988
<____ ____> For on-line help, type help();
|
#-->eq := p(n) = n*p(n-1) + p(n-2);
eq := p(n) = n p(n - 1) + p(n - 2)
# Try an asymptotic expansion in n of the default order
#-->asympt( rsolve(eq,p(n)), n );
_C1 GAMMA(n + 1)
1 1 1 17 1 1
(1 - 1/n + 1/2 ---- + 1/3 ---- + 1/24 ---- - ---- ---- + O(----))
2 3 4 40 5 6
n n n n n
# where _C1 is an arbitrary constant set by the initial conditions.
# (There is another term in the expansion, also multiplied by an
# arbitrary constant, but this term is of a smaller asymptotic
# order and will never affect the expansion of the first one,
# here are a few terms of it:
n 1 1 1 1
_C2 (-1) (1 + 1/n - 3/2 ---- + 5/3 ---- + 1/24 ---- + O(----))
2 3 4 5
n n n n
-----------------------------------------------------------------
GAMMA(n + 2)
#
# The asymptotic series in 1/n does not look familiar, and does
# not appear to have any simplification. Here are a few more
# terms for your entertainment:
#-->asympt( rsolve(eq,p(n)), n, 11 );
_C1 GAMMA(n + 1)
1 1 1 17 1 749 1
(1 - 1/n + 1/2 ---- + 1/3 ---- + 1/24 ---- - ---- ---- - ----- ----
2 3 4 40 5 720 6
n n n n n
3623 1 7447 1 494575 1 103174741 1
- ------ ---- - ------- ---- + -------- ---- + ----------- -----
2520 7 40320 8 72576 9 3628800 10
n n n n
1
+ O(-----))
11
n
Gaston Gonnet
DVD: There followed a reference to the book mentioned in note 93.0,
another not-the-Fibonacci-sequence reply to the earlier mistake,
a comment about a different sequence, and then this:
Newsgroups: sci.math
Path: decwrl!ucbvax!bloom-beacon!tut.cis.ohio-state.edu!osupyr.mast.ohio-state.edu!gae
Subject: Re: finder of lost sequences
Posted: 25 Apr 88 12:49:58 GMT
Organization: The Ohio State University, Dept. of Math.
> p[1] = 1
> p[2] = 2
> p[n] = n p[n-1] + p[n-2]
Would you accept a "closed form" in terms of Bessel functions or some such?
--
Gerald A. Edgar [email protected]
Department of Mathematics [email protected]
The Ohio State University ...{akgua,gatech,ihnp4,ulysses}!cbosgd!osupyr!gae
Columbus, OH 43210 70715,1324 CompuServe
DVD: Well, I have six more mail messages that "SEARCH" claims touch
this topic; I will post them soon. So what's that last person
know about Bessel functions and Stan's sequence? ... :-)
Dan
|
| Here's the rest of the USENET sci.math postings on this
topic. The first doesn't seem related to the sequence in
question. The others start off related and slowly drift
away. :-) The third one deals with the Bessel function
question from .-1. The asterisks separating them are
mine.
Dan
************************************************************
Newsgroups: sci.math
Path: decwrl!labrea!agate!pasteur!ames!ll-xn!mit-eddie!uw-beaver!tektronix!reed!justin
Subject: Re: finder of lost sequences
Posted: 26 Apr 88 01:43:32 GMT
Organization: Reed College, Portland OR
Let a(0)=1 b(0)=-1
a(1)=0 b(1)=2
And, for n>1, let a(n)=a(n-2)-(2n-1)*a(n-1).
Also, let the same recursion relation hold for b(n).
Then {a(n)/b(n)} --> -exp(-2). The only "proof" i have for this is that the
coefficients were derived from expanding the exponential function on [-1,1] in
Legendre polynomials. The sequence converges quite quickly, though the frac-
tion is not always in lowest terms. Does anybody have a decent proof for this?
nitsuJ --
************************************************************
Newsgroups: sci.math
Path: decwrl!sun!pitstop!sundc!seismo!uunet!mcvax!lambert
Subject: Re: finder of lost sequences
Posted: 26 Apr 88 13:40:48 GMT
Organization: CWI, Amsterdam
In article <[email protected]> [email protected] (Finder
of Lost Sequences) writes (on the sequence: p[1] = 1; p[2] = 2;
p[n] = n p[n-1] + p[n-2]):
) It's asymptotically C*n! (...)) where C is some) constant i know to many
) decimal places but that's it.
In fact, a good asymptotic approximation is provided by C*n!/exp(1/n),
where C = 1.5906368588358... .
--
Lambert Meertens, CWI, Amsterdam; [email protected]
************************************************************
Newsgroups: sci.math
Path: decwrl!labrea!sri-unix!husc6!mailrus!umix!uunet!mnetor!utzoo!utgpu!water!watmath!watdragon!ghgonnet
Subject: Re: finder of lost sequences
Posted: 26 Apr 88 19:16:09 GMT
Organization: U of Waterloo, Ontario
>
> Would you accept a "closed form" in terms of Bessel functions or some such?
>
Just yesterday, in a private mail to desJardins and Rabinowitz, I noted
that i^n Jn(2i) (where i^2+1=0), follows the same recursion formula.
This solution, however, corresponds to the asymptotically smallest
solution of the recurrence. (see my previous posting on the asymptotic
solutions of the recurrence).
Gaston Gonnet.
************************************************************
Newsgroups: sci.math
Path: decwrl!labrea!eos!ames!ll-xn!husc6!im4u!tut.cis.ohio-state.edu!osupyr.mast.ohio-state.edu!gae
Subject: Re: finder of lost sequences
Posted: 27 Apr 88 12:12:56 GMT
Organization: The Ohio State University, Dept. of Math.
In article <[email protected]> [email protected] (Lambert Meertens) writes:
>In article <[email protected]> [email protected] (Finder
>of Lost Sequences) writes (on the sequence: p[1] = 1; p[2] = 2;
>p[n] = n p[n-1] + p[n-2]):
>) It's asymptotically C*n! (...)) where C is some) constant i know to many
>) decimal places but that's it.
>In fact, a good asymptotic approximation is provided by C*n!/exp(1/n),
>where C = 1.5906368588358... .
>
Here it is to 50 places: (It's a value of a hyperbolic Bessel function)
1.5906368546\ 3732906338\ 2254424999\ 6662479544\ 7815949554-
--
Gerald A. Edgar [email protected]
Department of Mathematics [email protected]
The Ohio State University ...{akgua,gatech,ihnp4,ulysses}!cbosgd!osupyr!gae
Columbus, OH 43210 70715,1324 CompuServe
************************************************************
Newsgroups: sci.math
Path: decwrl!labrea!agate!pasteur!ames!ll-xn!mit-eddie!bbn!rochester!pt.cs.cmu.edu!andrew.cmu.edu!jk3k+
Subject: Re: finder of lost sequences
Posted: 27 Apr 88 19:22:03 GMT
Organization: Carnegie Mellon
In-Reply-To: <[email protected]>
OK, here's what i've got so far. We find
j[n]=(-1)^n*sum(i=0,inf){1/(i!*(i+n+1)!)} is an exact solution of the
recurrence. We also find k[n]=(-1)^n*j[-2-n] (continuing j) is another
solution to the recurrence. I've not found a series for k, but there's a nice
approximation k[n]=2*j[-1]*j[0]*sum(i=0,n){(-1)^i*(n-i)!/i!}+O(1/(n+1/2)!).
The original sequence is approximated by omitting the factor of 2*j[-1].
--Joe
************************************************************
Newsgroups: sci.math
Path: decwrl!sun!pitstop!sundc!seismo!uunet!portal!cup.portal.com!doug-merritt
Subject: Re: finder of lost sequences
Posted: 3 May 88 00:12:57 GMT
Organization: The Portal System (TM)
XPortal-User-Id: 1.1001.4407
Lambert recently commented about a bug in his C compiler due to
inaccuracy in the 14 decimal of a constant. No smiley face attached
to his posting.
Not to worry, Lambert...that much inaccuracy is to be expected.
Numerical functions are rarely accurate to the final decimal.
The fifty digit number quoted was probably inaccurate in *its*
final decimal as well.
BTW that number was driving me crazy; I'm fairly sure it came up
in a different context (as a root of a superexponential function)
but I can't find it in any of my notes. Oh well.
Doug Merritt ucbvax!sun.com!cup.portal.com!doug-merritt
or ucbvax!eris!doug ([email protected])
or ucbvax!unisoft!certes!doug
************************************************************
Newsgroups: sci.math
Path: decwrl!labrea!bloom-beacon!tut.cis.ohio-state.edu!osupyr.mast.ohio-state.edu!gae
Subject: Re: finder of lost sequences
Posted: 4 May 88 12:11:36 GMT
Organization: The Ohio State University, Dept. of Math.
In article <[email protected]> [email protected] writes:
>
>The fifty digit number quoted was probably inaccurate in *its*
>final decimal as well.
>
It is NOT. (Barring software bugs.)
>BTW that number was driving me crazy; I'm fairly sure it came up
>in a different context (as a root of a superexponential function)
>but I can't find it in any of my notes. Oh well.
It is sum (n=0 to infinity) 1/n!(n+1)!
The convergence is very rapid, making it ideal for multi-digit
computation.
--
Gerald A. Edgar [email protected]
Department of Mathematics [email protected]
The Ohio State University ...{akgua,gatech,ihnp4,ulysses}!cbosgd!osupyr!gae
Columbus, OH 43210 70715,1324 CompuServe
************************************************************
Newsgroups: sci.math
Path: decwrl!hplabs!hp-sdd!ucsdhub!esosun!seismo!uunet!mcvax!lambert
Subject: Re: finder of lost sequences
Posted: 5 May 88 00:41:38 GMT
Organization: CWI, Amsterdam
In article <[email protected]> [email protected] writes:
) Lambert recently commented about a bug in his C compiler due to
) inaccuracy in the 14 decimal of a constant. No smiley face attached
) to his posting.
It was more like the 9th decimal :-(
) Not to worry, Lambert...that much inaccuracy is to be expected.
) Numerical functions are rarely accurate to the final decimal.
I used only arithmetic functions like + and /. It was a genuine bug in the
optimizer: code was moved too enthusiastically, causing the lower half of a
double to get clobbered. This was the C compiler of 4.3BSD on an HCX-7.
Without -O option I got accuracy to 15 decimals, as I had a right to expect.
) BTW that number was driving me crazy; I'm fairly sure it came up
) in a different context (as a root of a superexponential function)
) but I can't find it in any of my notes. Oh well.
Something that would be really useful: an analogon to Sloane's handbook of
integer sequences, but now for real constants. The criterion for inclusion
should be pragmatical; so sqrt(2/pi) for example has a place, but sin(1+pi)
probably not, unless someone can show how it pops up in a natural way as
some constant in a genuine problem (not fabricated to give rise to the
constant). With the current state of networking, it seems to me that it
would be feasible to build up a database of constants in an incremental
fashion by a world-wide cooperative effort if someone volunteers to set up
the database (including software) and do some moderation (lest some fool
contributes zillions of uninteresting constants).
--
Lambert Meertens, CWI, Amsterdam; [email protected]
************************************************************
Newsgroups: sci.math
Path: decwrl!labrea!sri-unix!husc6!bloom-beacon!mit-eddie!bbn!rochester!pt.cs.cmu.edu!andrew.cmu.edu!jk3k+
Subject: Re: finder of lost sequences
Posted: 5 May 88 17:50:16 GMT
Organization: Carnegie Mellon
In-Reply-To: <[email protected]>
I've thought about making a library of numerical constants. But i've got a
question: what would be a good hashing function? A simple one i thought of is
fractional part. That way pi and pi+1 and pi-137 all map to the same place.
If you fold it in half, you get negatives to go to the same place. I've got
some better ideas, but let's hear yours.
--Joe
************************************************************
Newsgroups: sci.math
Path: decwrl!ucbvax!agate!brahms!desj
Subject: Re: finder of lost sequences
Posted: 7 May 88 00:59:16 GMT
Organization: UC Berkeley Math Dept
In article <[email protected]> [email protected] (Joe Keane) writes:
>I've thought about making a library of numerical constants. But i've got a
>question: what would be a good hashing function? A simple one i thought of is
>fractional part. That way pi and pi+1 and pi-137 all map to the same place.
>If you fold it in half, you get negatives to go to the same place. I've got
>some better ideas, but let's hear yours.
You are taking the quotient of the reals by the integers. But
rational numbers in general are boring, so why not quotient out the
reals by the rationals? Unfortunately this would make it hard to look
things up :-).
-- David desJardins
|