# How to solve the system of recurrence equations

The system has the form

$$(n-2)f_n^{(1)}=n(f_{n-1}^{(1)}+1),$$ $$(n-2\cdot 2) f_n^{(2)}=n(f_{n-1}^{(2)}+f_{n-1}^{(1)}),$$ $$\ldots$$ $$(n-2k)f_n^{(k)}=n(f_{n-1}^{(k)}+f_{n-1}^{(k-1)}),$$ for the unknown sequences $f_n^{(1)},f_n^{(2)},\ldots,f_n^{(k)}$ with the initial conditions $f^{(i)}_k=0,$ for all $k=0,1,\ldots,2i.$

By direct calculation I have got

$$f_n^{(1)}=n(n-2),$$ $$f_n^{(2)}=\frac{1}{2!} (n-4) { n \choose 2} (3n-7),$$ $$f^{(3)}_n=\frac{1}{3!} (n-6) { n \choose 3} \left( 19{n}^{2}-141n+254 \right),$$ $$f^{(4)}_n=\frac{1}{4!} (n-8) { n \choose 4} \left( 211{n}^{3}-3258{n}^{2}+16481n-27306 \right),$$ $$f^{(5)}_n=\frac{1}{5!} (n-10) { n \choose 5} \left( 3651{n}^{4}-96550{n}^{3}+946185{n}^{2}-4071950n+ 6492024 \right)$$

Question. What is a general expression for $f_n^{(i)}$?

The ordinary generating function for the above sequences has the form $$G(f_n^{(1)},z)={\frac {{z}^{3} \left( 3-z \right) }{ \left( 1-z \right) ^{3}}}=3{z}^{3}+8{z}^{4}+15{z}^{5}+\cdots$$ $$G(f_n^{(2)},z)={\frac {z^5(-3{z}^{3}+16{z}^{2}-35z+40)}{ \left( 1-z \right) ^{5}}},$$ $$G(f_n^{(3)},z)={\frac {{z}^{7} \left( -40{z}^{5}+288{z}^{4}-897{z}^{3}+1575{z} ^{2}-1701z+1155 \right) }{ \left( 1-z \right) ^{7}}}$$

-
Where this system comes from? –  Daniele Zuddas Apr 27 '12 at 18:57
You might want to restate your question without typos. As it reads, I get $f_n^{(1)}=-n/2$, which is clearly not what you intend. –  Michael Renardy Apr 27 '12 at 19:00
to Michael. Sorry, corrected –  Melania Apr 27 '12 at 19:07
I don't know that this'll help, but the sequence 3,19,211,3651 shows up at oeis.org/A000275 with next term 90921. –  Barry Cipra Apr 27 '12 at 19:11
to Barry. Thanks. I already saw it but it doesnt help. –  Melania Apr 27 '12 at 19:20

This is not a full solution, but it reduces the system to another recurrence relation which involves only coefficients. Let $$f_n^{(k)}=a_0^k n(n-1)...(n-k+1)+a_1^k n(n-1)...(n-k)+...+a_k^k n(n-1)...(n-2k+1).$$ Then the above system reduces to $$a_i^k={a_i^{k-1}\over i-k}$$ for $i < k$ and $a_k^k$ is determined by the condition that $f_{2k}^{(k)}=0$. Clearly the determination of $a_k^k$ is the difficult part. But if the sequence 3,19 etc. shows up elsewhere, that should be suggestive.
Addendum: If all the $a_i^k$ are expressed in terms of $a_i^i$, then the recurrence relation for the $a_k^k$ becomes the same as for the Taylor coefficients of the reciprocal Bessel function mentioned in Barry Cipra's link.