HMMT 2003 U30

The sequence $a_{1}, a_{2}, a_{3}, \ldots$ of real numbers satisfies the recurrence

$$a_{n+1}=\frac{a_{n}^{2}-a_{n-1}+2 a_{n}}{a_{n-1}+1} .$$

Given that $a_{1}=1$ and $a_{9}=7$, find $a_{5}$.