prove n = Big-O(1) using induction

Question

I know that the relation n = Big-O(1) is false. But if we use induction involving Big-O it can be proved. But the fallacy is we cannot induct Big-O. But my question is how we can disprove the relation by using the constants.

The false proof is here, please give me the proof of it being false using the constants. I'm getting confused with the constants, I don't know whether each relation used in the proof is having different constant or the same. Please enlighten on the topic.

TO prove: n= O(1)
for n=1 , 1= O(1) proved

induction hypothesis : let it is true : n-1 = O(1) now we prove that n = O(1)

LHS :  n = (n-1) + 1 
         =  O(1) + 1
         =  O(1) + O(1)
         =  O(1) 

Falsely proved.. I want the clarification of the fallacy in terms of <= and constants, that is in the basic definition of Big-O.

Answer 1

One thing you have to understand here is that Big-O or simply O denotes the 'rate' at which a function grows. You cannot use Mathematical induction to prove this particular property.

One example is

O(n^2) = O(n^2) + O(n)

By simple math, the above statement implies O(n) = 0 which is not. So I would say do not use MI for this. MI is more appropriate for absolute values.

Answer 2

The big O notation is about functions, so statements like 1 = O(1) have no meaning. What you are proving here is that if you take an arbitrary n and the constant function f(x) = n then f = O(1) which is true and gives no contradiction. There is no problem with the proof, the problem is that you are confusing the constant function f(x) = n with the function f(n) = n. For the latter we have that f = O(n) and if you try to prove it with your method you'll see that it won't work.

Answer 3

If you need to do any rigorous proofs involving Big-O notation, you need to start with the format definition of Big-O In a proof you can't just say O(1) + 1 = O(1). You need to do the proof in terms of the formal definition. To prove that a function (f(n) = n for example) is O(1), you need to find unique x0 and M that match the definition. You can demonstrate this through induction, and you can also do a proof by contradiction using the definition to show that f(n) = n is not O(1)

Just as Olathe stated in his answer, you can't just add Big-O sets and functions. Start with the formal definition of what classifies a function as a member of a particular Big-O set.