A friend sent this recreational maths problem:
Let $a_0=0$ and $a_1=1$. If $a_n=n(a_{n-1}+3a_{n+1})$, compute $\sum_{n\ge 0}a_n$.
My current work: Since this is not your classic linear recurrence, you can't use the characteristic polynomial method. I tried Engineer's induction, but the terms didn't seem to follow a pattern of any sort (I listed values for both $a_n$ and $\sum_{n=0}^{i}a_n$ and got nowhere).
It would be great if someone could give me a hint as to solving this.
Let $f(x) = \displaystyle \sum_{n=0}^\infty a_n x^n$. Then: $$\begin{array}{rcl} f(x) &=& \displaystyle \sum_{n=0}^\infty a_n x^n \\ x f(x) &=& \displaystyle \sum_{n=0}^\infty a_{n-1} x^n \\ x^{-1} f(x) &=& \displaystyle \sum_{n=0}^\infty a_{n+1} x^n \\ (x + 3x^{-1}) f(x) &=& \displaystyle \sum_{n=0}^\infty (a_{n-1} + 3a_{n+1}) x^n \\ (x + 3x^{-1}) f'(x) + (1-3x^{-2}) f(x) &=& \displaystyle \sum_{n=0}^\infty n (a_{n-1} + 3a_{n+1}) x^{n-1} \\ (x^2 + 3) f'(x) + (x-3x^{-1}) f(x) &=& \displaystyle \sum_{n=0}^\infty n (a_{n-1} + 3a_{n+1}) x^n \\ \end{array}$$ So we obtain the differential equation: $$f(x) = (x^2 + 3) f'(x) + (x-3x^{-1}) f(x)$$ Which we now solve: $$\begin{array}{rcl} (x^2 + 3) f'(x) + (x-3x^{-1}) f(x) &=& f(x) \\ (x^2 + 3) f'(x) &=& (1-x+3x^{-1}) f(x) \\ \dfrac{f'(x)}{f(x)} &=& \dfrac{1-x+3x^{-1}}{x^2+3} \\ (\ln f)' &=& \dfrac{x-x^2+3}{x(x^2+3)} \\ \ln f &=& -\log(x^2+3) + \log(x) + \dfrac1{\sqrt3} \arctan\left(\dfrac{x}{\sqrt3}\right) + C \\ f(x) &=& e^C \dfrac{x}{x^2+3} \exp\left( \dfrac1{\sqrt3} \arctan\left(\dfrac{x}{\sqrt3}\right) \right) \end{array}$$
Given the constraint $a_1 = 1$ we know $e^C = 3$, so: $$f(x) = \dfrac{3x}{x^2+3} \exp\left( \dfrac1{\sqrt3} \arctan\left(\dfrac{x}{\sqrt3}\right) \right)$$
So $a_n$ can be found from the Taylor series expansion of $f$.