Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.