Find witnesses (or not)

Question

I have just started learning Analysis of Algorithms and I came across these set of questions:

1. Find witnesses c and m such that rⁿ⁺¹ = O(rⁿ) for r>1
2. Show that there are no witnesses for n² = O(n)
3. From 2, deduce no witnesses for 2²ⁿ = O(2ⁿ)

So, I have tackled some as:

1. 
   rⁿ⁺¹ ≤ rⁿ⁺¹
   rⁿ⁺¹ ≤ r.rⁿ
   rⁿ⁺¹ ≤ (r+1).rⁿ
   Therefore, c = r + 1; m = 1
   
   
2. 
   n² ≤ n²
   No value for c satisfies the above inequality, therefore no witnesses (??)
   
   
3. 
   2²ⁿ ≤ 2²ⁿ
   No value for c satisfies the above inequality, therefore no witnesses (??)

I am not sure how to go about the last 2. Can anyone please tell me whether what I have done is correct?

Thanks.

Answer 1

Part 1 looks OK.

For part 2, to show no witnesses exist, you have to proceed by contradiction. Assume witnesses $c,m$ exist, so we have $n^2 \leq cn$ for all $n\geq m$. Now, to reach a contradiction, find at least one value of $n \geq m$ for which $n^2 > cn$. The value for $n$ can be defined in terms of $c,m$. It shouldn't be too hard to find one.

For part 3, the text suggests to use 2. That is, to prove that if we had (by contradiction) witnesses for 3, we could derive from them some witnesses for 2.

(Honestly, to me this way sounds harder than simply tackling 3 on its own, without exploiting 2. Maybe you were introduced to some theorem which can apply here to shorten the exercise? I have no idea.)