import
4.code.options;

import 4.code.about;

class Header{
}

import 4.code.about;

class Header{

public void title(){

String fullTitle = "// - ";

}
class
Thread
extends
Board{

public void EmptyTitle(OP Anonymous){

}
String fullTitle = "EmptyTitle";

int postNumber = "575412";

String image = "Capture.png";

String date = "10/10/18(Wed)14:24:50";

String comment = "How is this even considered a question? this is 2nd year cs proofs btw. would like hints more than just the full answer but idk where to even start. do i find a c1, c2 that bound the fxn? how do i do that and then what. im totally lost";

"You can see immediately that the sum is less than n^{k+1} because there are n terms, each bounded by n^k.

On the other hand, the sum is greater than n * (n/2)^k. = 2^{-k} n^{n+1}. So you just have to prove that.";

">>575452

More details (don't read if you don't want spoilers):

Prove that

(a-i)^k + (a+i)^k >= 2a^k

by expanding the terms on the left using the Binomial theorem. Use this to prove that the original sum

1^k + 2^k + ... + (n/2)^k + ... + ... + (n-1)^k + n^k

is greater than

(n/2)^k + (n/2)^k + ... + (n/2)^k + ... + (n/2)^k + (n/2)^k

= n * (n/2)^k.

I assume you understand what Θ means.";

">>575454

>I assume you understand what Θ means.

uh... the... Eye of Sauron?";

"What language is this?";

">>575608

math";

">>575452

> 2^{-k} n^{n+1}

Dat is een oef";

">>575593

>>I don't understand what Θ means

If you didn't know that it was an uppercase theta, that means you're incapable of using google and therefore not fit to be a CS major. In which case, kill yourself.";

">>576058

>2^{-k} n^{n+1}

You're right, it should say 2^{-k} n^{k+1}.

>>576059

pls no bully";

">>575412

for the lower bound it's easier to throw away the first half of the terms < (n/2)^k and bound the remaining by below by (n/2)^k, so you obtain:

sum >= (n/2)(n/2)^k = 2^(-k-1) n^(k+1)";

}