From: rjohnson@apple.com (Robert Johnson) Newsgroups: sci.math Subject: Re: recursive relation Date: 29 Jan 1995 03:09:51 -0800 Summary: give a couple of methods of solution In article , Jeff Ylvisaker wrote: >I am interested in finding a means to solve recursive relations >that are of the form: > Asubn = f(n) + Asub(n-1). >In particular the relation for summing up the squares of the >first n integers: > Asubn = n^2 + Asub(n-1). _Euler-Maclaurin Sum Formula_ In general, use the Euler-Maclaurin Sum Formula. It is based on the fact that, formally, the Taylor series for F(x-1) is -D e F(x) [1] where D is d/dx. Thus, if f(x) = F(x) - F(x-1), then -D f(x) = (1 - e ) F(x) [2] If we "solve" [2] for F(x), we get D -1 F(x) = ------- D f(x) [3] -D 1 - e where D^-1 is indefinite integration (complete with constant of integration). The differential operator D/(1 - e^-D) is 1 1 2 1 4 1 6 1 8 1 10 1 + - D + -- D - --- D + ----- D - ------- D + -------- D - ... [4] 2 12 720 30240 1209600 47900160 We get [4] by plugging D into x/(1 - e^-x). In the case of f(n) = n^2, [3] and [4] give 3 2 2 n + 3 n + n F(n) = --------------- [5] 6 _Binomial Coefficients_ Another way to do this for polynomials is based on the formula for the generation of Pascal's Triangle: C(n+1,m+1) = C(n,m) + C(n,m+1) [6] If we consider C(n,m) = n(n-1)(n-2)...(n-m+1)/m! as an mth degree polynomial in n, then n --- \ > C(k,m) = C(n+1,m+1) [7] / --- k=0 Using [6], [7] follows easily by induction on n. Thus, because n^2 = 2 C(n,2) + C(n,1), [7] says that 3 2 2 n + 3 n + n F(n) = 2 C(n+1,3) + C(n+1,2) = --------------- [8] 6 Rob Johnson Apple Computer, Inc. rjohnson@apple.com