finding a solution for this recurrence relation

This is not a well-posed problem. In other words, given $a_0=0$, the value of $a_1$ can be any real number whatsoever since it must satisfy $$ 0 \cdot a_1 = 1 \cdot a_0 + 0 \cdot 1, $$ and both sides are $0$ for any value of $a_1$, so the equality holds. In other words, the specified conditions do not uniquely specify a sequence.

Given the value of $a_1$ you have $a_n = n(n-1) + na_1$ for all $n\ge 0.$ The recursion equation $$n a_{n+1} = (n+1) a_n+n(n+1)\tag{1}$$ for $n=0$ is just $a_0=0.$ In other words, you should start with initial condition for $a_1$ and then all other values of $a_n$ for $n>1$ are determined, and also $a_0=0.$

If you want to solve for $n<0$, then given the value of $a_{-1}$ you have the equation $a_n = n(n-1) + na_{-1}$ which determines $a_n$ for all $n<0.$