Recursive relation, and its boundary

Question

Is there any way to solve $na_{n}=(1+n)a_{n-1}+2n-1$ Or, at least to show $a_{n}<2n\ln(n)$ if $a_{0}=0$

Answer 1

We have $\displaystyle \frac{a_n}{n+1}=\frac{a_{n-1}}n+\frac3{n+1}-\frac1n$

\begin{align*} \sum_{k=1}^n\frac{a_k}{k+1}&=\sum_{k=1}^n\frac{a_{k-1}}k+3\sum_{k=1}^n\frac1k+\frac3{n+1}-3-\sum_{k=1}^n\frac1k\\ \frac{a_n}{n+1}&=a_0+2\sum_{k=1}^n\frac1k-\frac {3n}{n+1}\\ a_n&=(n+1)a_0-3n+2(n+1)\sum_{k=1}^n\frac1k\\ &=-3n+2(n+1)\sum_{k=1}^n\frac1k \end{align*}

Answer 2

Well $$na_n=(n+1)a_{n-1}+2n-1$$ $$\implies (n-1)a_{n-1}=na_{n-2}+2n-3$$ Subtracting them gives $$na_n-(n-1)a_{n-1}=(n+1)a_{n-1}-na_{n-2}+2$$ $$\iff a_n=2a_{n-1}-a_{n-2}+\frac{2}{n}$$

Noting, of course, that $a_0=0 \implies a_1=1$

Does this help?