Question

Let \(k\)be a positive integer. Show that \({1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{ is }}O({n^{k + 1}})\).

Short answer

By using mathematical operations on \({1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{ }}\), we prove that \({1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{ is }}O({n^{k + 1}})\).

Step-by-step solution

Step 1:

Let \(k\) be a positive integer.

Using \({1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{ }}\), we get that,

\(|{1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{ }}| = {1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{ }}\),

Now

\(\begin{array}{l} \Rightarrow |{1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{|}} \le {n^k} + {n^k} + {n^k} + ... + {n^k}\\ \Rightarrow |{1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{|}} \le n.{n^k}\\ \Rightarrow |{1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{|}} \le {n^{k + 1}}\\ \Rightarrow |{1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{|}} \le 1.|{n^{k + 1}}|\end{array}\)

Step 2:

Now, if we compare \( \Rightarrow |{1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{|}} \le 1.|{n^{k + 1}}|\) with the definition of Big-O Notation that is

\(|f(x)| \le C|g(x)|\), we can imply that

\({1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{ is }}O({n^{k + 1}})\)with constants \(C = 1{\rm{ and }}k = 1\).

We have shown that \({1^k} + {2^k} + \cdot \cdot \cdot + {n^k}{\rm{ is }}O({n^{k + 1}})\)with constants \(C = 1{\rm{ and }}k = 1\).