2

I came across the following recurrence relation, and was wondering if there might be some way to get a closed form:

$F\left(0\right)=0$

$F\left(1\right)=1$

$F\left(n\right)=F\left(n-1\right)+\left(\frac{2}{n}\right)F\left(n-2\right)$

Rodrigo de Azevedo
  • 1
user357891
  • 153

1 Answers1

2

The DE associated with the recurrence relation $$ n a_n = n a_{n-1} + 2 a_{n-2} \tag{1} $$ is given by $$ x f' = xf+x^2 f'+2x^2 f \tag{2}$$ that is separable. By solving it we get that our coefficients depend on the coefficient of the Taylor series of $$g(x)=\frac{e^{-2x}}{(1-x)^3}\tag{3}$$ in a neighbourhood of zero, that can be computed by convolution. By stars and bars and the fact that $g(x)$ has a triple pole at $x=1$ we have that the sequence $\{a_n\}$ behaves like a second-degree polynomial in $n$ plus a small perturbation, so it is way different from the Fibonacci sequence.

Jack D'Aurizio
  • 353,855
  • Really fascinated by this answer. How do you know that the DE is $x f' = xf+x^2 f'+2x^2 f \tag{2}$? How do you solve it and determine that the coefficients depend on the Taylor series of $g(x)=\frac{e^{-2x}}{(1-x)^3}\tag{3}$? – user51819 Aug 02 '16 at 18:04
  • 1
    @user51819: standard techniques. Have a look at Generatingfunctionology by Wilf. – Jack D'Aurizio Aug 02 '16 at 18:05
  • This file here explains all of this? https://www.math.upenn.edu/~wilf/gfologyLinked2.pdf – user51819 Aug 02 '16 at 18:16
  • 1
    @user51819: and much more. It is a recommended lecture for anyone. – Jack D'Aurizio Aug 02 '16 at 18:17
  • Thanks! Any other recommendations? – user51819 Aug 02 '16 at 18:26
  • 2
    @user51819: another interesting book about this branch of combinatorics is Flajolet - Analytic combinatorics. It goes deeper on the theory of asymptotic expansions through the saddle point method, for instance. – Jack D'Aurizio Aug 02 '16 at 18:29
  • 2
    So one solves the problem, gives book recommendations and still gets downvoted. Thank you, ******les. – Jack D'Aurizio Aug 02 '16 at 18:58
  • Just for the record I upvoted you everywhere in this comment chain + the answer; so it was not me – user51819 Aug 02 '16 at 19:05
  • Is it possible to expand on the fact that $F\left(n\right)$ "behaves like a second-degree polynomial" and provide a more concrete formula for it? – user357891 Aug 02 '16 at 19:08