if supposing that the premises are true and the conclusion is false we are able to arrive at a contradiction(a conclusion that is contradictory to our assumptions or something obviously untrue like 1=0)=>our conclusion must be true!

Let P be a predicate that is defined for integers n. Suppose Basis stepP(a)is true for some particular integer a; Inductive step For all integers k>=a, if P(k)is true, then P(k+1)is true. Then P(n)is true for all integers n>=a