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.

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.

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.

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.