I know this is some sort of "common-sense" question, but I want to get a clear boundary on this: when can I apply / cannot apply induction on a proof?
For example, I know that:
Ex1) A person with 1 hair is bald.
If a person has n hair and is bald, he is bald even when he has n+1 hair.
is a wrong application of induction.
Similarly, induction doesn't work on big-Os.
SO my question is, are there any "axiomatic idea" or anything that defines the boundary on when induction can be applied?
Thanks : )
Induction works for all formal predicates on natural numbers.
It's ok that induction fails for the predicate bald(n) (where n is the number of hairs a person has) because notions like this are not formal, they are just rough classifications (not really the realm of mathematics).