Big theta question

Hi,

I'm trying to show that $\frac{n(n+1)}{2}-1$ is big theta(n^2). Is it as simple as this:

$K_{1}\leq\frac{n(n+1)}{2}-1 \leq K_{2}$

$2+2K_{1}\leq n(n+1)\leq 2+2K_{2}$

$2+2K_{1}\leq n^2+n \leq 2+2K_{2}$

Then as n tends to infinity the n squared factor increases much faster, so it's big theta n squared for some constants K1 and K2?

That's not really a proof. You've shown that if there are $K_1, K_2$ such that $2+2K_{1}\leq n^2+n \leq 2+2K_{2}$ then it is big theta(1). You're actually aiming for $K_{1} n^2 \leq\frac{n(n+1)}{2}-1 \leq K_{2} n^2$ - do you see why?

I don't . Could you explain it a bit more please. Thank you.

I'm completely new to this.

Should have said

Suppose $\frac{n(n+1)}{2}$ is $\Theta(n^2)$. Then there exist constants $c, C$ such that $c n^2 \leq \frac{n(n+1)}2 \leq C n^2$ for $n$ sufficiently large. Can you then discover what $c, C$ actually are?

Should have said

Suppose $\frac{n(n+1)}{2}$ is $\Theta(n^2)$. Then there exist constants $c, C$ such that $c n^2 \leq \frac{n(n+1)}2 \leq C n^2$ for $n$ sufficiently large. Can you then discover what $c, C$ actually are?

I'll have an attempt. Not too sure how to go about it though, also are you missing a -1 in between the inequalities?

Do c and C have to be positive?

is it 1/2 ?. I re arranged each inequality for c and then did the limit as n tends to infinity so took the ratio of the n^2...

Yes on both counts - sorry



$c n^2 \leq \dfrac{n(n+1)}{2}-1 \leq C n^2$; $c=\frac{1}{2}$ gives $\frac{n^2}{2} \leq \frac{n^2}{2} + \frac{n}{2} - 1$ for the lower inequality, which is true as long as n is sufficiently large (bigger than 1). So yes, c=1/2 will do. (Note that the constant is not unique - 1/4 would also do. 1/2 is the best bound there is here.)

For the upper bound: notice that both c and C can't be the same thing - otherwise you're asserting that $\frac{n(n+1)}{2}$ is precisely $\frac{1}2 n^2$ for sufficiently large n, and that's false. You're going to need C to be bigger. Have a guess? Can you show your guess works?

Can C just be 1. Because then you have 1/2+1/2-1<1 i.e. 0<1

Yep, exactly. (Indeed, *any* C will do, as long as it's strictly bigger than 1/2.)

Now you've found the appropriate c, C. Mathematical pedantry: the proof started out "suppose that the function is $\Theta(n^2)$". That is, we assumed what we wanted to prove. We need to make sure that all the steps are iff rather than just implications (although this might be hard because several C, c will do, so some of our steps won't be "only if"). Alternatively, we could re-write the proof, starting out from "let c=1/2, C = 1".

Ah okay. Thanks so much. So just to clarify it would go something along the lines of:

Proof:

Let $cn^2\leq \frac{n(n+1)}{2}-1 \leq Cn^2$ from some constants c, C.

This implies that $c \leq \frac{n(n+1)}{2n^2} -1$. Then the limit as n tends to infinity is 1/2 therefore c=1/2. Then apply a similar argument for C?

Strictly speaking you need to show that the limiting process behaves well. For instance, the sequence 1, 2-1/2, 3+1/3, 4-1/4, … is $\Theta(n)$ according to your argument, but the function is not $\Theta(n)$ with constant c=1 because the terms alternate between below and above n. Constant 1/2 would do there, though.

In this case, any c strictly less than 1/2 will do - that's what you've shown. You could, for instance, say "limit is 1/2, so as n increases, the RHS approaches 1/2 n^2; hence c = 1/4 will do".

Can C just be 1. Because then you have 1/2+1/2-1<1 i.e. 0<1

Hi thanks for all your help . I was just re-reading through and I understand it all apart from one thing. When we assumed C=1, why did we sub the value of 1 in for n... that's the one part I don't get which obviously leads to 0<1 so the inequlity holds.

Ah, I didn't read your answer properly - that line should read $\frac{n^2+n}{2}-1 \leq n^2$ (letting C = 1), whence subtracting $\frac{n^2}2$ from both sides will give you an inequality which holds for sufficiently large n.

What you have done *could* have been a proof - as long as you also show that equality holds with the inequality only for n<0. (You'd do that by solving the quadratic equation $\frac{n^2+n}{2}-1 = n^2$.) That would then be like drawing a plot of the function (n against $\frac{n(n+1}2 - 1 - n^2$), and showing that it intersects the n-axis only for n<0; then observing that at n=0 the function lies above the n-axis, so it must also lie above the n-axis for n>0. That turns out to work in this case, because in fact the inequality is always satisfied for all real n, but it's a bit less safe as a method - it might not work so easily in all cases.

Ah okay I get that, but then don't you have to find out what the sufficently large values of n actually are? Otherwise it seems like you're just saying this holds for some large number. :P. Seen as my proof doesn't have to be particularly rigorous I'm happy with just subtracting and using the above though.

Well, you could just say "the values exist, because n^2 gets bigger than n" - that's probably enough for these purposes. To be strictly rigorous, you'd need to find the sufficiently large values, yes.

Thank so much for all the help. Legend.