I am reading the following proof and I am having trouble understanding this line of reasoning.
n∑i=1ik≤n∑i=1nk=n∗nk
However, I do not understand how the second summation simplifies to n∗nk. Where is the i in the second summation to iterate? And without it, how can we even sum anything?
Answer
n∑i=1nk=nk+⋯+nk⏟n times=nk(1+⋯+1⏟n times)=nk⋅n
Identities to remember: ∑ni=11=n(add 1 n times)∑ni=1kai=k∑ni=1ai(factoring out a constant) Putting those together you get n∑i=1k=kn∑i=11=kn In this case nk is just a constant (with respect to i).
No comments:
Post a Comment