Newsgroups: sci.math From: gathe@ul.ie (Eugene Gath) Subject: Help with a recurrence relation. Date: Tue, 31 Oct 1995 16:54:58 GMT I recently came across the recurrence relation: $\gamma_0=1$, $$ \gamma_k=1-2\sum_{j=0}^{k-1} {k\choose j} \gamma_j $$ for $k>0$. So $\gamma_1=-1$, $\gamma_2=3$, $\gamma_3=-13$, etc. I know that the Bernouilli numbers satisfy $$ B_k=-\sum_{j=0}^{k-1} {k\choose j} B_j $$ which is vaguely similar. My question is whether there is either a closed form solution for the $\gamma$s or whether they can be expressed in terms of some "well-known" numbers such as the $B_k$s. Please send me e-mail directly to gathe@ul.ie Thanks, Eugene Gath ============================================================================== Date: Mon, 6 Nov 95 14:59:56 CST From: rusin (Dave Rusin) To: gathe@ul.ie Subject: Re: Help with a recurrence relation. Newsgroups: sci.math In article you write: >I recently came across the recurrence relation: $\gamma_0=1$, >$$ >\gamma_k=1-2\sum_{j=0}^{k-1} {k\choose j} \gamma_j >$$ >for $k>0$. >So $\gamma_1=-1$, $\gamma_2=3$, $\gamma_3=-13$, etc. >I know that the Bernouilli numbers satisfy >$$ >B_k=-\sum_{j=0}^{k-1} {k\choose j} B_j >$$ >which is vaguely similar. >My question is whether there is either a closed form solution for the >$\gamma$s or whether they can be expressed in terms of some "well-known" >numbers such as the $B_k$s. I don't know quite what you expect to get in the way of formulas, but you're right to see a resemblence. Let F(X)=Sum_{k >= 0} gamma_k/k! X^k, and similarly Ber(X)=Sum_{k >= 0} a_k/k! X^k, where a_k=0 for k odd >1, a_1=(-1/2), and a_(2n) = (-1)^(n-1) B_(2n). Then it is known that Ber(X) = X/(e^X-1). On the other hand, your recurrence relation (times X^k/k!, summed over all k >= 0) gives F(X) = e^X - 2(e^X-1)F(X), so that F(X) = 1/(2-e^(-X)) after some simplification (I'm being cavalier here about convergence). You can now finagle the Bernoulli numbers in here: F(-X) = 1/(1-[e^X-1]) = 1/(1-[X/Ber(X)]) = Ber(X)/(Ber(X)-X) = 1 + X/(Ber(X)-X) or if you prefer you can use Ber(-X)=Ber(X)+X to get F(X) = 1 - X/(Ber(X)+2X) So you can (roughly) invert 1 + (3/2)X + B_2/2! X^2 - B_4/4! X^4 +... to compute each gamma_k in terms of the B_j with j <= k. Alternatively, the relation now is (1-F(X))*(Ber(X)+2X) = X which shows that for each k, a certain linear combination of the products of B_j and gamma_(k-j) vanishes. If I've done it right, we have for k>1: (3k/2) gamma_(k-1) + Sum_(0 <= i < k-1) (k choose i) gamma_i a_(k-i)=0 But I don't think that's any nicer than the recurrence you started with! dave ============================================================================== From: Eugene Gath * To: rusin Subject: Re: Help with a recurrence relation. Date: Mon, 06 Nov 95 23:07:00 GMT Hi Dave, thanks for your reply. Here is an edited version of my latest sci.math posting which has an error in the generating function (an extra 1). The motivation behind all this is to get a nice form for: the asymptotic behaviour, as $N \rightarrow\infty$, of $$ \sum_{m=1}^{N} m^l 2^m $$ We define this to be: $$\sum_{m=1}^{N} m^l 2^m \sim 2^{N+1}N^l \sum_{k=0}^l \frac{\gamma_k}{N^k}{l\choose k} $$ One then finds that $\gamma_k$ is defined recursively by $$ \gamma_k=1-2\sum_{l=0}^{k-1}{k\choose j}\gamma_j $$ and $\gamma_0=1$. So, for example, $\gamma_1=-1$, $\gamma_2=3$, $\gamma_3=-13$, $\gamma_4=75$. The exponential generating function $$ \sum_{k=0}^\infty \frac{\gamma_k z^k}{k!} = \frac{e^z+1}{2e^z-1} $$ [You have corrected my error: an extra 1 in the numerator] >>$$ >>B_k=-\sum_{j=0}^{k-1} {k\choose j} B_j >>$$ My first posting had this wrong too: It should be B_k=-(1/(k+1))\sum_{j=0}^{k-1} {k+1\choose j} B_j >I don't know quite what you expect to get in the way of formulas, but I don't know either -it's just that the resemblance is reasonably strong. > F(X) = 1 - X/(Ber(X)+2X) Another possibility might be to use F(X)=1/2(1+Ber(X+ln2)/(X+ln20), but maybe this is JUST going around in circles? Thanks for taking the time to look at this. Eugene Gath, University of Limerick, Ireland. ==============================================================================