chap mathematical preliminaries proving either variant of the induction step (in conjunction with verifying the base caseyields satisfactory proof by mathematical induction the two conditions that make up the induction proof combine to demonstrate that thrm holds for as an extension of the fact that thrm holds for this factcombined again with condition ( or ( )indicates that thrm also holds for and so on thusthrm holds for all values of (larger than the base casesonce the two conditions have been proved what makes mathematical induction so powerful (and so mystifying to most people at firstis that we can take advantage of the assumption that thrm holds for all values less than to help us prove that thrm holds for this is known as the induction hypothesis having this assumption to work with makes the induction step easier to prove than tackling the original theorem itself being able to rely on the induction hypothesis provides extra information that we can bring to bear on the problem there are important similarities between recursion and induction both are anchored on one or more base cases recursive function relies on the ability to call itself to get the answer for smaller instances of the problem likewiseinduction proofs rely on the truth of the induction hypothesis to prove the theorem the induction hypothesis does not come out of thin air it is true if and only if the theorem itself is trueand therefore is reliable within the proof context using the induction hypothesis it do work is exactly the same as using recursive call to do work example here is sample proof by mathematical induction call the sum of the first positive integers (ntheorem (nn( )/ proofthe proof is by mathematical induction check the base case for verify that ( ( )/ ( is simply the sum of the first positive numberwhich is because ( )/ the formula is correct for the base case state the induction hypothesis the induction hypothesis is ( - = ( )(( ( )( use the assumption from the induction hypothesis for to show that the result is true for the induction hypothesis states