the purpose of induction After getting an answer (in a comment) from peter for this question I have a follow up question. 
If, in all horses are the same color problem for example, we need to use reason, reason which is specific to the case, in order to find that "hole" between the correct base case and the correct inductive step. That "hole" where n=2 which makes the proof collapse.
So how can we verify that our hypotheses are correct and that there are no "holes"?
I mean if we proved the base case p(0) or p(1) or p((int)whatever) is true and the inductive step is true, how can be sure that there no "holes" in the hypothesis?
Do we use induction only to prove what we know, beyond any doubt, is true?
But doesn't that contradicts the purpose of a proof?
I know this is such a Newbie question.. but I have searched for answers for these specific questions and I could not find..
Thank you all!

You can prove statements inductively from which you did not know before being true or false.
You just need to make sure that there is no "hole" in your proof.
In the case of your example the problem occured because the proof of the inductive step was simply wrong.
But if you check that both p(0) and the inductive step can be proved formally correct then your proof will be valid and you don't need to search for "holes" afterwards.
