The sequence is given by the following formula: $$(n+3)a_{n+2}=(6n+9)a_{n+1}-na_n$$ with $a_0=1$ and $a_1=2$. Show that all terms of this sequence are integers.
I have an original solution for this problem (next, will be briefly outlining that).
It first determines a generating function $\big(f(x)=\sum_{n=0}^\infty a_nx^n \big)$ and finds its explicit form in some neighborhood of $0$. Namely, $$f(x)=\frac{1-x-\sqrt{x^2-6x+1}}{2x}, \ \ |x|<3- \sqrt 2$$ Then, says this function satisfies the quadratic equation $xt^2-(1-x)t+1=0$.
After some operations with it, they end up with obtaining another recurrence formula for $(a_n)$ as follows: $$a_{n+1}=a_n + \sum_{k=0}^n a_k a_{n-k}$$ Obviously, an easy induction will complete the proof now.
However, I'd like to know if one could approach this by some other methods/thinking. The reason why I'm curious is that this solution gets quite a messy appearance while finding the form of $f(x)$ and I don't think this beautiful problem has no other rather attractive approach.
By the way, the OS says proving that it's an increasing sequence is an easy job and skipping that part. Maybe it is really easy but I'm troubled to show...
Any help is appreciated.