Actually induction is not necessary. To show that "x" has the same order of "y", prove o(y)<=o(x) first, and then next o(x)<=o(y). Fortunately each one of the three cases is symmetric, i.e. you don't need to do anything to prove o(x)<=o(y) since you already got o(y)<=o(x)