I'm looking for the tightest upper and lower bounds on the sequence defined recursively by $a_{0}=1$ and $a_{n}={\displaystyle \sum_{k=0}^{n-1}\frac{4}{n^{2}}a_{k}+c\cdot n}$ for $c>0$. It is obvious that $a_{n}\in\Omega\left(n\right)$ and I managed to show that $a_{n}\in O\left(n\log n\right)$ but I'm not sure if either is tight.
Help would be appreciated!
Hint: Show by induction that $a_n\leqslant(7c+3)n+2c+1$ for every $n\geqslant0$.
Thus, $a_n=\Theta(n)$. Furthermore, $\frac{a_n}n\to c$.
Edit: To see that $a_n=O(n)$ is direct once one knows that $a_n=O(n\log n)$ since using $a_n=O(n\log n)$ in the recursion yields $a_n\leqslant\frac4{n^2}\sum\limits_{k\leqslant n}k\log k+cn=cn+O(\log n)$. But it is not necessary to assume that $a_n=O(n\log n)$ to proceed. To wit, once one got the idea that $a_n=O(n)$, one can try to confirm this idea by establishing an upper bound $a_n\leqslant\alpha n+\beta$ which is both true at $n=0$ (this is so if $\beta\geqslant1$) and hereditary. Thus, one wants that, for every $n\geqslant1$, $$ \alpha n+\beta\geqslant\frac4{n^2}\sum_{k=0}^{n-1}(\alpha k+\beta)+cn=\frac2{n}\alpha(n-1)+\frac4n\beta+cn. $$ If $n=1$, this reads $\alpha\geqslant3\beta+c$. In general, the condition reads $$ (\alpha-c)n^2-(2\alpha-\beta)n+2\alpha-4\beta\geqslant0, $$ which, using $n^2\geqslant2n$ if $n\geqslant2$, is guaranteed as soon as $$ (\beta-2c)n+2\alpha-4\beta\geqslant0. $$ If $\beta\geqslant2c$, since we already assumed that $\alpha\geqslant3\beta+c$, the LHS is at least $2(\beta-2c)+2(3\beta+c)-4\beta=4\beta-2c\geqslant0$.
Finally the property $a_n\leqslant\alpha n+\beta$ is true for $n=0$ and hereditary if $\beta\geqslant1$, $\alpha\geqslant3\beta+c$, and $\beta\geqslant2c$, for example if one chooses the values of $\alpha$ and $\beta$ in the hint.