From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: How to solve A_n = (n-1)A_{n-1} + (n-2)A_{n-2} in a closed form ?
Date: 26 Apr 1995 16:22:18 GMT
In article <1995Apr24.061918.22609@dec8.ncku.edu.tw>,
wrote:
[Solve A_n = (n-1)A_{n-1} + (n-2)A_{n-2} in a closed form]
> where A_1 = A_2 = 1.
How explicit do you need it to be? I'll give you three choices.
The usual approach using generating functions is awkward since the resulting
series converges for no x except x=0: the coefficients grow too fast.
Indeed, let B_n = A_n/(n-1)!. Then you see
B_n = B_(n-1) + B_(n-2)/(n-1)
so that B_n is at least log(n) or so, making A_n comparable to n!.
But with this transformation life is not so bad. The series
F(X) = Sum( B_n/(n+1) X^(n+1), n >= 1 )
will converge in some interval around zero (since B_n < B_(n-1) + B_(n-2)
makes B_n less than a Fibonacci series, and so B_n is bounded by a
multiple of some c^n ). We can then manipulate its power series term-by-term:
F'(X) = Sum( B_n X^n, n>=1 )
so that (1-X)*F'(X) = X*F(X) + B_1*X.
Hence F is the solution to the differential equation
(1-X) F' - X F = X
F(0) = 0
which is
F(X) = exp(-X)/(X-1) - 1
Multiplying the power series of the two factors, I see the coefficient
of X^n in F(X) is the finite sum
Sum( (-1)^i / i! , i=0...n )
so that this is B_(n-1)/n, and then A_n = (n-1)! B_n is
[ANSWER #1]
A_n = (n+1)*(n-1)!*Sum( (-1)^i / i!, i=0...n+1)
I typed this into maple to check and got a surprise:
> A[n]:=(n+1)*(factorial(n-1))*sum((-1)^i/factorial(i), i=0..n+1);
[ANSWER #2]
/ (n + 2) \
| (-1) hypergeom([1], [3 + n], -1)|
A[n] := (n + 1) (n - 1)! |exp(-1) - ---------------------------------------|
\ (n + 2)! /
So I guess this is a "closed form", all right, but you might want this info too
>?hypergeom
FUNCTION: hypergeom - generalized hypergeometric function
CALLING SEQUENCE:
hypergeom([n1, n2, ... ], [d1, d2, ... ], z)
PARAMETERS:
[n1, n2, ... ] - list of numerator coefficients
[d1, d2, ... ] - list of denominator coefficients
SYNOPSIS:
- The function hypergeom(n, d, z) is the generalized hypergeometric function
F(n, d, z). This function is also known as Barnes's extended hypergeometric
function. If there are j coefficients in n, and k coefficients in d, this
function is also known as jFk.
- The definition of F(n, d, z) is
sum ( (product( GAMMA( n[i]+k ) / GAMMA( n[i] ), i=1..j)*z^k )
/ (product( GAMMA( d[i]+k ) / GAMMA (d[i] ), i=1..m)*k! ), k=0..infinity)
where j is the number of terms in the list [n1, n2, ... ] and m is the number
of terms in the list [d1, d2, ...].
- If n[i] = -m, a non-positive integer, the series stops after m terms.
etc.
Whether this is a useful "closed form" or not is, I suppose, a matter of
taste.
An alternative is to take maple's hint and compare the sum to exp(-1).
The difference is an alternating, decreasing sequence, hence bounded by
the first term. Thus we see A_n differs from (n+1)*(n-1)!*exp(-1)
by at most 1/[n(n+2)] (after a little simplification). Knowing that
A_n is integral, we may write
[ANSWER #3]
A_n = nearest integer to exp(-1) * (n+1)!/n.
This works quite well.
dave