[a / b / c / d / e / f / g / gif / h / hr / k / m / o / p / r / s / t / u / v / vg / vr / w / wg] [i / ic] [r9k / s4s / vip / qa] [cm / hm / lgbt / y] [3 / aco / adv / an / asp / bant / biz / cgl / ck / co / diy / fa / fit / gd / hc / his / int / jp / lit / mlp / mu / n / news / out / po / pol / qst / sci / soc / sp / tg / toy / trv / tv / vp / wsg / wsr / x] [Settings] [Search] [Home]
Board
/wsr/ - Worksafe Requests

File: Capture.png (9 KB, 679x120)
9 KB PNG
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)

Delete Post: [File Only] Style: