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>,
 <l1883104@sparc12.cc.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