-1

i am trying to prove that $n^2= \theta(5n^2 + n)$ And i'm using this formula:

$c_1(5n^2 + n) ≤ n^2 ≤ c_2(5n^2 + n)$ $\forall n ≥ n_0$

Is it true? If it's true could you please help me for find the c1,c2 and n0. I found them but i'm not sure are they true or false. Thank you.

As for my attempt, in the comments it was pointed out that $n^2\leq 5n^2+n$ is already true for all positive $n$, that's why my mind confused about the $c_2$. I found the $c_1$ is $\frac{1}{5}$ and $n_0= 5$ but I'm not sure are they true or false

JMoravitz
  • 79,518
syntax
  • 11
  • 2
    "I found them but I'm not sure are they true or false" What did you find? I will point out that we do not require that these values be strict and there are infinitely many equally correct answers that you could give. A bit point of problems like this is to be creative. – JMoravitz Oct 08 '19 at 13:53
  • As a hint, $n^2\leq 5n^2+n$ is already true for all positive $n$. Meanwhile $5n^2+n\leq 6n^2$ is also true for all positive $n$. Do you see why and how this can lead you to one of the many possible solutions? – JMoravitz Oct 08 '19 at 13:54
  • Yes as you said n2≤5n2+n is already true for all positive n, that's why my mind confused about the c2. I found the c1 is 1/5 and n0= 5 but I'm not sure are they true or false. – syntax Oct 08 '19 at 14:36
  • $n^2 \leq \color{blue}{1}\cdot (5n^2+n)$... As for $c_1$ being $\frac{1}{5}$, that is not small enough. Notice that $\frac{1}{5}(5n^2+n) = n^2+\frac{n}{5}$ is always greater than $n^2$. – JMoravitz Oct 08 '19 at 14:38
  • Oh you're right, so c1 might be 1/6 ? We are searching a upper bound for c1 right? And could you please give me an idea about n0? – syntax Oct 08 '19 at 14:46

1 Answers1

0

One among many valid final answers (and the easiest to see in my opinion) is to try to use $n_0=1$ and choose the values of $c_1,c_2$ accordingly.

We notice that $n^2\leq 1\cdot (5n^2+n)$ is true for all $n$ so setting $c_2=1$ suffices. This just follows from "if I add a positive number to another positive number then I make it bigger" as well as "if I multiply a positive number bigger than $1$ to another positive number then I make it bigger", properties that you should be well familiar with already.

Now, on the other side, we have that $5n^2+n \leq 5n^2+n^2 = 6n^2$ is true for all positive $n$ as well. This, again following from the earlier mentioned properties. By dividing both sides of this inequality by six, we arrive at $\frac{5}{6}(5n^2+n)\leq n^2$.

We have as a result, one of the many possible choices for $c_1,c_2,n_0$ as being $c_1=\frac{1}{6},c_2=1,n_0=1$ as we have that:

$$\frac{1}{6}(5n^2+n)\leq n^2\leq 1(5n^2+n)~~~~\forall n\geq 1$$

Now, as mentioned, you could have used many other choices for $c_1,c_2,n_0$. The end result for this specific problem is that you could let $c_1$ and $c_2$ be any values such that $0<c_1<\frac{1}{5}$ and $c_2\geq\frac{1}{5}$ and then let $n_0$ be however big it needed to be in order to let that work. $c_1$ being equal to $\frac{1}{5}$ is not small enough. However, none of that actually matters. All that was necessary for this problem was to find any example that works, and the one above does that just fine.

JMoravitz
  • 79,518
  • I was thinking the same thing as you about the c2 after your comment, yes they are many other choices but we are looking for a upper bound for c1 and lower bound for c2 right? That's why 1/6 and 1 solved my problem. Thank you so much! – syntax Oct 08 '19 at 15:08
  • We are not looking for upper and lower bounds. If you are actually interested in upper and lower bounds that would be 1/5 in both cases. – JMoravitz Oct 08 '19 at 15:16