Prove that $\frac{n^2}{2} - 3n = \Theta(n^2)$

Question

The question is,

Prove that $\frac{n^2}{2} - 3n = \Theta(n^2)$.

I understand that to do this I must determine positive constants $c_1$, $c_2$, and $n_0$ such that $$c_1n^2 \leq \frac{n^2}{2} - 3n \leq c_2n^2$$

I simplified by dividing by $n^2$ which left

$$c_1 \leq \frac{1}{2} - \frac{3}{n} \leq c_2$$

The book I am following along with says "We can make the right-hand inequality hold for any value of $n \geq 1$ by choosing any constant $c_2 \geq \frac{1}{2}$. Likewise, we can make the left-hand inequality hold for any value of $n \geq 7$ by choosing any constant $c_1 \leq \frac{1}{14}$."

I understand that there are other choices for the constants but I'm not sure of a method for determining them. What general procedure should I use for determining these other than guess and check?

Answer 1

What you did so far was good. Then, to determine an exact choice for the constants $c_1$ and $c_2$, you should think carefully about the expression, in this case $$ \frac{1}{2} - \frac{3}{n}. $$ As $n$ gets larger, what does this sequence do? Well, it gets closer and closer to $\frac12$. And it only increases; it gets closer to $\frac12$ from below.

That means we can pick the upper bound $c_2 = \frac12$. And since it increases, we can pick the lower bound $c_1$ to be the $n$th term for some suitably large $n$. In the book, they picked $n = 7$ to get $\frac{1}{2} - \frac{3}{7} = \frac{1}{14}$ as the lower bound.

Answer 2

Your task doesn't really require you to specify the constants. One approach for the solution would be to state that the sequence $$ \frac{1}{2} - \frac{3}{n} $$ converges to the constant $ \frac{1}{2} $. This means that for any $ \varepsilon > 0 $ there exists $ N(\varepsilon)$ such that $ \frac{1}{2} - \varepsilon < \frac{1}{2} - \frac{3}{n} < \frac{1}{2} + \varepsilon $ for $n > N(\varepsilon) $, which gives you the two constans for all sufficiently large $ n $ (i.e. larger than $ N(\varepsilon) $)

Answer 3

Lets find first constant: $$\begin{array}{l}\left| {\frac{{{n^2}}}{2} - 3n} \right| \le {c_1}.{n^2} \to if\;\;n \ge 6\;\;then\;\;\frac{{{n^2}}}{2} - 3n \ge 0\\So,\;we\;can\;say\;\;\frac{{{n^2}}}{2} - 3n \le {c_1}.{n^2}\;\;;\;\;n \ge 6\;\;instead\;of\;\left| {\frac{{{n^2}}}{2} - 3n} \right| \le {c_1}.{n^2}\\Let\;\;{c_1} = \frac{1}{2} \to \frac{{{n^2}}}{2} - 3n \le \frac{{{n^2}}}{2} \to - 3n \le 0 \to n \ge 0\;\;Obvious\end{array} % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaadaabda % qaamaalaaabaGaamOBamaaCaaaleqabaGaaGOmaaaaaOqaaiaaikda % aaGaeyOeI0IaaG4maiaad6gaaiaawEa7caGLiWoacqGHKjYOcaWGJb % WaaSbaaSqaaiaaigdaaeqaaOGaaiOlaiaad6gadaahaaWcbeqaaiaa % ikdaaaGccqGHsgIRcaWGPbGaamOzaiaaysW7caaMe8UaamOBaiabgw % MiZkaaiAdacaaMe8UaaGjbVlaadshacaWGObGaamyzaiaad6gacaaM % e8UaaGjbVpaalaaabaGaamOBamaaCaaaleqabaGaaGOmaaaaaOqaai % aaikdaaaGaeyOeI0IaaG4maiaad6gacqGHLjYScaaIWaaabaGaam4u % aiaad+gacaGGSaGaaGjbVlaadEhacaWGLbGaaGjbVlaadogacaWGHb % GaamOBaiaaysW7caWGZbGaamyyaiaadMhacaaMe8UaaGjbVpaalaaa % baGaamOBamaaCaaaleqabaGaaGOmaaaaaOqaaiaaikdaaaGaeyOeI0 % IaaG4maiaad6gacqGHKjYOcaWGJbWaaSbaaSqaaiaaigdaaeqaaOGa % aiOlaiaad6gadaahaaWcbeqaaiaaikdaaaGccaaMe8UaaGjbVlaacU % dacaaMe8UaaGjbVlaad6gacqGHLjYScaaI2aGaaGjbVlaaysW7caWG % PbGaamOBaiaadohacaWG0bGaamyzaiaadggacaWGKbGaaGjbVlaad+ % gacaWGMbGaaGzaVlaaysW7daabdaqaamaalaaabaGaamOBamaaCaaa % leqabaGaaGOmaaaaaOqaaiaaikdaaaGaeyOeI0IaaG4maiaad6gaai % aawEa7caGLiWoacqGHKjYOcaWGJbWaaSbaaSqaaiaaigdaaeqaaOGa % aiOlaiaad6gadaahaaWcbeqaaiaaikdaaaaakeaacaWGmbGaamyzai % aadshacaaMe8UaaGjbVlaadogadaWgaaWcbaGaaGymaaqabaGccqGH % 9aqpdaWcaaqaaiaaigdaaeaacaaIYaaaaiabgkziUoaalaaabaGaam % OBamaaCaaaleqabaGaaGOmaaaaaOqaaiaaikdaaaGaeyOeI0IaaG4m % aiaad6gacqGHKjYOdaWcaaqaaiaad6gadaahaaWcbeqaaiaaikdaaa % aakeaacaaIYaaaaiabgkziUkabgkHiTiaaiodacaWGUbGaeyizImQa % aGimaiabgkziUkaad6gacqGHLjYScaaIWaGaaGjbVlaaysW7caWGpb % GaamOyaiaadAhacaWGPbGaam4BaiaadwhacaWGZbaaaaa!D2D5! $$ According to the initial assumption: $$n \ge 6 \to {n_0} = 6,\;\;{c_1} = 0.5 \to \frac{{{n^2}}}{2} - 3n \le \frac{1}{2}{n^2}\;for\;any\;n \ge 6\;\;(A) % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaamOBaiabgw % MiZkaaiAdacqGHsgIRcaWGUbWaaSbaaSqaaiaaicdaaeqaaOGaeyyp % a0JaaGOnaiaacYcacaaMe8UaaGjbVlaadogadaWgaaWcbaGaaGymaa % qabaGccqGH9aqpcaaIWaGaaiOlaiaaiwdacqGHsgIRdaWcaaqaaiaa % d6gadaahaaWcbeqaaiaaikdaaaaakeaacaaIYaaaaiabgkHiTiaaio % dacaWGUbGaeyizIm6aaSaaaeaacaaIXaaabaGaaGOmaaaacaWGUbWa % aWbaaSqabeaacaaIYaaaaOGaaGjbVlaadAgacaWGVbGaamOCaiaays % W7caWGHbGaamOBaiaadMhacaaMe8UaamOBaiabgwMiZkaaiAdacaaM % e8UaaGjbVlaacIcacaWGbbGaaiykaaaa!672A! $$ Lets find second constant: $$\begin{array}{l}\left| {\frac{{{n^2}}}{2} - 3n} \right| \ge {c_2}.{n^2} \to if\;\;n \ge 6\;\;then\;\;\frac{{{n^2}}}{2} - 3n \ge 0\\So,\;we\;can\;say\;\;\frac{{{n^2}}}{2} - 3n \ge {c_2}.{n^2}\;\;;\;\;n \ge 6\;\;instead\;of\;\left| {\frac{{{n^2}}}{2} - 3n} \right| \ge {c_2}.{n^2}\\ \to (\frac{1}{2} - {c_2})\,{n^2} - 3n \ge 0 \to n \times ((\frac{1}{2} - {c_2})\;n - 3) \ge 0 \to \left\{ {\begin{array}{*{20}{c}}{n \le 0\;\; \times \quad \quad \quad }\\{Or}\\{n \ge 3/(0.5 - {c_2})}\end{array}} \right.\\ \to n \ge \frac{3}{{0.5 - {c_2}}}\;\;(B)\end{array} % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaadaabda % qaamaalaaabaGaamOBamaaCaaaleqabaGaaGOmaaaaaOqaaiaaikda % aaGaeyOeI0IaaG4maiaad6gaaiaawEa7caGLiWoacqGHLjYScaWGJb % WaaSbaaSqaaiaaikdaaeqaaOGaaiOlaiaad6gadaahaaWcbeqaaiaa % ikdaaaGccqGHsgIRcaWGPbGaamOzaiaaysW7caaMe8UaamOBaiabgw % MiZkaaiAdacaaMe8UaaGjbVlaadshacaWGObGaamyzaiaad6gacaaM % e8UaaGjbVpaalaaabaGaamOBamaaCaaaleqabaGaaGOmaaaaaOqaai % aaikdaaaGaeyOeI0IaaG4maiaad6gacqGHLjYScaaIWaaabaGaam4u % aiaad+gacaGGSaGaaGjbVlaadEhacaWGLbGaaGjbVlaadogacaWGHb % GaamOBaiaaysW7caWGZbGaamyyaiaadMhacaaMe8UaaGjbVpaalaaa % baGaamOBamaaCaaaleqabaGaaGOmaaaaaOqaaiaaikdaaaGaeyOeI0 % IaaG4maiaad6gacqGHLjYScaWGJbWaaSbaaSqaaiaaikdaaeqaaOGa % aiOlaiaad6gadaahaaWcbeqaaiaaikdaaaGccaaMe8UaaGjbVlaacU % dacaaMe8UaaGjbVlaad6gacqGHLjYScaaI2aGaaGjbVlaaysW7caWG % PbGaamOBaiaadohacaWG0bGaamyzaiaadggacaWGKbGaaGjbVlaad+ % gacaWGMbGaaGzaVlaaysW7daabdaqaamaalaaabaGaamOBamaaCaaa % leqabaGaaGOmaaaaaOqaaiaaikdaaaGaeyOeI0IaaG4maiaad6gaai % aawEa7caGLiWoacqGHLjYScaWGJbWaaSbaaSqaaiaaikdaaeqaaOGa % aiOlaiaad6gadaahaaWcbeqaaiaaikdaaaaakeaacqGHsgIRcaGGOa % WaaSaaaeaacaaIXaaabaGaaGOmaaaacqGHsislcaWGJbWaaSbaaSqa % aiaaikdaaeqaaOGaaiykaiaaykW7caWGUbWaaWbaaSqabeaacaaIYa % aaaOGaeyOeI0IaaG4maiaad6gacqGHLjYScaaIWaGaeyOKH4QaamOB % aiabgEna0kaacIcacaGGOaWaaSaaaeaacaaIXaaabaGaaGOmaaaacq % GHsislcaWGJbWaaSbaaSqaaiaaikdaaeqaaOGaaiykaiaaysW7caWG % UbGaeyOeI0IaaG4maiaacMcacqGHLjYScaaIWaGaeyOKH46aaiqaae % aafaqabeWabaaabaGaamOBaiabgsMiJkaaicdacaaMe8UaaGjbVlab % gEna0kaaywW7caaMf8UaaGzbVdqaaiaad+eacaWGYbaabaGaamOBai % abgwMiZkaaiodacaGGVaGaaiikaiaaicdacaGGUaGaaGynaiabgkHi % TiaadogadaWgaaWcbaGaaGOmaaqabaGccaGGPaaaaaGaay5Eaaaaba % GaeyOKH4QaamOBaiabgwMiZoaalaaabaGaaG4maaqaaiaaicdacaGG % UaGaaGynaiabgkHiTiaadogadaWgaaWcbaGaaGOmaaqabaaaaOGaaG % jbVlaaysW7caGGOaGaamOqaiaacMcaaaaa!F62C! $$ According to the initial assumption: $$\begin{array}{l}n \ge 6 \to \frac{3}{{0.5 - {c_2}}} \ge 6 \to \frac{1}{{0.5 - {c_2}}} \ge 2 \to 0 < 0.5 - {c_2} \le 0.5 \to - 0.5 < - {c_2} \le 0 \to {c_2} < 0.5\\Let\;\;{c_2} = \frac{1}{3}\;\;optionally \to Considering\;(B),\;we\;can\;say\;\;n \ge \frac{3}{{\frac{1}{2} - \frac{1}{3}}} \to n \ge 18\\n \ge 18 \to {n_0} = 18,\;\;{c_2} = \frac{1}{3} \to \frac{{{n^2}}}{2} - 3n \ge \frac{1}{3}{n^2}\;for\;any\;n \ge 18\;\;(C)\end{array} % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaWGUb % GaeyyzImRaaGOnaiabgkziUoaalaaabaGaaG4maaqaaiaaicdacaGG % UaGaaGynaiabgkHiTiaadogadaWgaaWcbaGaaGOmaaqabaaaaOGaey % yzImRaaGOnaiabgkziUoaalaaabaGaaGymaaqaaiaaicdacaGGUaGa % aGynaiabgkHiTiaadogadaWgaaWcbaGaaGOmaaqabaaaaOGaeyyzIm % RaaGOmaiabgkziUkaaicdacqGH8aapcaaIWaGaaiOlaiaaiwdacqGH % sislcaWGJbWaaSbaaSqaaiaaikdaaeqaaOGaeyizImQaaGimaiaac6 % cacaaI1aGaeyOKH4QaeyOeI0IaaGimaiaac6cacaaI1aGaeyipaWJa % eyOeI0Iaam4yamaaBaaaleaacaaIYaaabeaakiabgsMiJkaaicdacq % GHsgIRcaWGJbWaaSbaaSqaaiaaikdaaeqaaOGaeyipaWJaaGimaiaa % c6cacaaI1aaabaGaamitaiaadwgacaWG0bGaaGjbVlaaysW7caWGJb % WaaSbaaSqaaiaaikdaaeqaaOGaeyypa0ZaaSaaaeaacaaIXaaabaGa % aG4maaaacaaMe8UaaGjbVlaad+gacaWGWbGaamiDaiaadMgacaWGVb % GaamOBaiaadggacaWGSbGaamiBaiaadMhacqGHsgIRcaWGdbGaam4B % aiaad6gacaWGZbGaamyAaiaadsgacaWGLbGaamOCaiaadMgacaWGUb % Gaam4zaiaaysW7caGGOaGaamOqaiaacMcacaGGSaGaaGjbVlaadEha % caWGLbGaaGjbVlaadogacaWGHbGaamOBaiaaysW7caWGZbGaamyyai % aadMhacaaMe8UaaGjbVlaad6gacqGHLjYSdaWcaaqaaiaaiodaaeaa % daWcaaqaaiaaigdaaeaacaaIYaaaaiabgkHiTmaalaaabaGaaGymaa % qaaiaaiodaaaaaaiabgkziUkaad6gacqGHLjYScaaIXaGaaGioaaqa % aiaad6gacqGHLjYScaaIXaGaaGioaiabgkziUkaad6gadaWgaaWcba % GaaGimaaqabaGccqGH9aqpcaaIXaGaaGioaiaacYcacaaMe8UaaGjb % VlaadogadaWgaaWcbaGaaGOmaaqabaGccqGH9aqpdaWcaaqaaiaaig % daaeaacaaIZaaaaiabgkziUoaalaaabaGaamOBamaaCaaaleqabaGa % aGOmaaaaaOqaaiaaikdaaaGaeyOeI0IaaG4maiaad6gacqGHLjYSda % WcaaqaaiaaigdaaeaacaaIZaaaaiaad6gadaahaaWcbeqaaiaaikda % aaGccaaMe8UaamOzaiaad+gacaWGYbGaaGjbVlaadggacaWGUbGaam % yEaiaaysW7caWGUbGaeyyzImRaaGymaiaaiIdacaaMe8UaaGjbVlaa % cIcacaWGdbGaaiykaaaaaa!E390! $$ Finally: $$\begin{array}{l}(A),\;(C) \to \frac{1}{3}{n^2} \le \frac{{{n^2}}}{2} - 3n \le \frac{1}{2}{n^2}\;\;for\;any\;n \ge 18\\ \to if\;\;{c_1} = \frac{1}{2},\;\;{c_2} = \frac{1}{3}\;\;and\;{n_0} = 18\;\;then\;we\;can\;say:\\\exists {c_1},\;{c_2},\;{n_0},\;\;\forall n \ge {n_0} \to {c_2}.{n^2} \le \frac{{{n^2}}}{2} - 3n \le {c_1}.{n^2} \to \frac{{{n^2}}}{2} - 3n \in \theta \;({n^2})\end{array} % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacaGGOa % GaamyqaiaacMcacaGGSaGaaGjbVlaacIcacaWGdbGaaiykaiabgkzi % UoaalaaabaGaaGymaaqaaiaaiodaaaGaamOBamaaCaaaleqabaGaaG % OmaaaakiabgsMiJoaalaaabaGaamOBamaaCaaaleqabaGaaGOmaaaa % aOqaaiaaikdaaaGaeyOeI0IaaG4maiaad6gacqGHKjYOdaWcaaqaai % aaigdaaeaacaaIYaaaaiaad6gadaahaaWcbeqaaiaaikdaaaGccaaM % e8UaaGjbVlaadAgacaWGVbGaamOCaiaaysW7caWGHbGaamOBaiaadM % hacaaMe8UaamOBaiabgwMiZkaaigdacaaI4aaabaGaeyOKH4QaamyA % aiaadAgacaaMe8UaaGjbVlaadogadaWgaaWcbaGaaGymaaqabaGccq % GH9aqpdaWcaaqaaiaaigdaaeaacaaIYaaaaiaacYcacaaMe8UaaGjb % VlaadogadaWgaaWcbaGaaGOmaaqabaGccqGH9aqpdaWcaaqaaiaaig % daaeaacaaIZaaaaiaaysW7caaMe8Uaamyyaiaad6gacaWGKbGaaGjb % Vlaad6gadaWgaaWcbaGaaGimaaqabaGccqGH9aqpcaaIXaGaaGioai % aaysW7caaMe8UaamiDaiaadIgacaWGLbGaamOBaiaaysW7caWG3bGa % amyzaiaaysW7caWGJbGaamyyaiaad6gacaaMe8Uaam4Caiaadggaca % WG5bGaaiOoaaqaaiabgoGiKiaadogadaWgaaWcbaGaaGymaaqabaGc % caGGSaGaaGjbVlaadogadaWgaaWcbaGaaGOmaaqabaGccaGGSaGaaG % jbVlaad6gadaWgaaWcbaGaaGimaaqabaGccaGGSaGaaGjbVlaaysW7 % cqGHaiIicaWGUbGaeyyzImRaamOBamaaBaaaleaacaaIWaaabeaaki % abgkziUkaadogadaWgaaWcbaGaaGOmaaqabaGccaGGUaGaamOBamaa % CaaaleqabaGaaGOmaaaakiabgsMiJoaalaaabaGaamOBamaaCaaale % qabaGaaGOmaaaaaOqaaiaaikdaaaGaeyOeI0IaaG4maiaad6gacqGH % KjYOcaWGJbWaaSbaaSqaaiaaigdaaeqaaOGaaiOlaiaad6gadaahaa % WcbeqaaiaaikdaaaGccqGHsgIRdaWcaaqaaiaad6gadaahaaWcbeqa % aiaaikdaaaaakeaacaaIYaaaaiabgkHiTiaaiodacaWGUbGaeyicI4 % SaeqiUdeNaaGjbVlaacIcacaWGUbWaaWbaaSqabeaacaaIYaaaaOGa % aiykaaaaaa!C7F2! $$