I am reading the following proof and I am having trouble understanding this line of reasoning.
$$ \sum_{i=1}^n i^k \leq \sum_{i=1}^nn^k = n* n^k $$
However, I do not understand how the second summation simplifies to $n* n^k$. Where is the $i$ in the second summation to iterate? And without it, how can we even sum anything?
Answer
$$\sum_{i=1}^nn^k = \underbrace{n^k+ \cdots + n^k}_{n\text{ times}} = n^k(\underbrace{1+ \cdots + 1}_{n\text{ times}}) = n^k\cdot n$$
Identities to remember: $$\begin{array}{lr}\sum^n_{i=1} 1 = n & \text{(add $1$ $n$ times)} \\ \sum^n_{i=1} ka_i = k\sum^n_{i=1} a_i & \text{(factoring out a constant)}\end{array}$$ Putting those together you get $$\sum^n_{i=1} k = k\sum_{i=1}^n 1 = kn$$ In this case $n^k$ is just a constant (with respect to $i$).
No comments:
Post a Comment