# Looking for bounds of a recursively defined sequence

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!

-
Is $c\cdot n$ also being summed? – Zen Jun 2 '13 at 21:02
$cn$ is outside of the sum. – Serpahimz Jun 2 '13 at 21:04

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.

-
Of course, coming up with something like $(7c+3)n + 2c + 1$ the hard part of the problem, and giving an answer to the hard part of the problem isn't much of a hint! – Hurkyl Jun 2 '13 at 21:43
I'm less concerned with the hint being quite thick and more interested with how exactly one comes up with that evaluation of $a_n$ (and such evaluations in general) – Serpahimz Jun 2 '13 at 21:49
Nice, thanks for the detailed explanation. I have another question regarding this: I worked quite hard to show that $a_{n}\in O\left(n\log n\right)$. It would be nice to see a a way to get directly to the result that $a_{n}\in O\left(n\right)$. – Serpahimz Jun 3 '13 at 7:24
The hypothesis that $a_n\in O(n\log n)$ is not used to prove that $a_n\in O(n)$. I reformulated the part of my answer explaining this. – Did Jun 3 '13 at 9:02