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