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

There is a huge logical fallacy hidden here:

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

n is a function and Ο(1) is a set of functions. Neither is a number (and induction proofs are all about proving things for a whole bunch of individual numbers in one fell swoop). The use of equal signs, like n = Ο(1), is an informal shorthand for f ∈ Ο(1), where f(x) = x.

This proof uses the fallacy of equivocation in two ways:

• by pretending that n is a number (the next number in the inductive journey) rather than an entire function
• by pretending the equal signs mean that two numbers are equal, which is what it means in an induction proof, instead of being a shorthand for element-of

If you want to see more clearly why this proof fails, replace n with another notation for a function, f (where f(x) = x), and the equal signs with element-of signs where needed and see if the proof still makes sense.

Base case:

let h(x) = 1 in
          h ∈ Ο(1)        [Any function is in Ο(that function)]

Inductive case:

          n = (n - 1) + 1 [Algebraic identity]
      n - 1 = n - 1       [Arithmetic]

let f(x) = x
    g(x) = f(x) - 1 in
          g ∈ Ο(1)        [Assume g ∈ Ο(1) because a different function, h, was]
          f ∈ Ο(1 + 1)    [By definition of Ο]
          f ∈ Ο(2)        [Arithmetic]

It becomes much clearer that this is not an induction proof at all. It's not even a valid proof in its own right, because we only proved that h ∈ Ο(1), which has nothing to do with whether g ∈ Ο(1), since those functions act very, very differently from each other.