maths learner
Badges: 3
Rep:
?
#1
Report Thread starter 5 years ago
#1
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?
0
reply
maths learner
Badges: 3
Rep:
?
#2
Report Thread starter 5 years ago
#2
bump.
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#3
Report 5 years ago
#3
(Original post by maths learner)
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?
0
reply
maths learner
Badges: 3
Rep:
?
#4
Report Thread starter 5 years ago
#4
(Original post by Smaug123)
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.

Oh is it because I want to show its big theta(n^2) so since the K1 and K2 are just constants, then multiplying them by n^2 gives a proportionality factor... I know what I mean but not sure how to word it aha. Or for that matter how to actually prove this is big theta(n^2). I'm completely new to this.
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#5
Report 5 years ago
#5
(Original post by maths learner)
I don't . Could you explain it a bit more please. Thank you.
The statement that f(x) is \Theta(g(x)) is precisely the statement that there are constants c, C such that c g(x) \leq f(x) \leq C g(x) for sufficiently large x.
You have apparently shown that there are constants c, C such that 2+2 c \leq n^2 + n \leq 2+2C. (This is false, by the way, and it's false because your first line is false.)

Essentially, you started from a false premise, and derived a conclusion which is both false and unrelated to the problem at hand.

The appropriate starting line is:

Spoiler:
Show
The following lines are equivalent. c x^2 \leq \dfrac{x(x-1)}{2} - 1 \leq C x^2

Intentionally there is only one line; you're meant to fill in the equivalent following lines.
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#6
Report 5 years ago
#6
(Original post by maths learner)
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?
0
reply
maths learner
Badges: 3
Rep:
?
#7
Report Thread starter 5 years ago
#7
(Original post by Smaug123)
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?
0
reply
maths learner
Badges: 3
Rep:
?
#8
Report Thread starter 5 years ago
#8
(Original post by Smaug123)
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?
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...
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#9
Report 5 years ago
#9
(Original post by maths learner)
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?
Yes on both counts - sorry


(Original post by maths learner)
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...
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?
0
reply
maths learner
Badges: 3
Rep:
?
#10
Report Thread starter 5 years ago
#10
(Original post by Smaug123)
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
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#11
Report 5 years ago
#11
(Original post by maths learner)
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".
0
reply
maths learner
Badges: 3
Rep:
?
#12
Report Thread starter 5 years ago
#12
(Original post by Smaug123)
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?
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#13
Report 5 years ago
#13
(Original post by maths learner)
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".
0
reply
maths learner
Badges: 3
Rep:
?
#14
Report Thread starter 5 years ago
#14
(Original post by Smaug123)
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".
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.
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#15
Report 5 years ago
#15
(Original post by maths learner)
Can C just be 1. Because then you have 1/2+1/2-1<1 i.e. 0<1
(Original post by maths learner)
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.
0
reply
maths learner
Badges: 3
Rep:
?
#16
Report Thread starter 5 years ago
#16
(Original post by Smaug123)
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.
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#17
Report 5 years ago
#17
(Original post by maths learner)
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.
1
reply
maths learner
Badges: 3
Rep:
?
#18
Report Thread starter 5 years ago
#18
(Original post by Smaug123)
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.
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#19
Report 5 years ago
#19
(Original post by maths learner)
Thank so much for all the help. Legend.
No problem
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • Bournemouth University
    Undergraduate Open Day Undergraduate
    Wed, 19 Feb '20
  • Buckinghamshire New University
    Postgraduate and professional courses Postgraduate
    Wed, 19 Feb '20
  • University of Warwick
    Warwick Business School Postgraduate
    Thu, 20 Feb '20

Has your university offer been reduced?

Yes (15)
28.3%
No (28)
52.83%
Don't know (10)
18.87%

Watched Threads

View All