proofproof by contradiction step contrary assumptionassume that there is largest integer call it (for "biggest"step show this assumption leads to contradictionconsider is an integer because it is the sum of two integers alsoc bwhich means that is not the largest integer after all thuswe have reached contradiction the only flaw in our reasoning is the initial assumption that the theorem is false thuswe conclude that the theorem is correct related proof technique is proving the contrapositive we can prove that by proving (not (not proof by mathematical induction mathematical induction is much like recursion it is applicable to wide variety of theorems induction also provides useful way to think about algorithm designbecause it encourages you to think about solving problem by building up from simple subproblems induction can help to prove that recursive function produces the correct result within the context of algorithm analysisone of the most important uses for mathematical induction is as method to test hypothesis as explained in section when seeking closed-form solution for summation or recurrence we might first guess or otherwise acquire evidence that particular formula is the correct solution if the formula is indeed correctit is often an easy matter to prove that fact with an induction proof let thrm be theorem to proveand express thrm in terms of positive integer parameter mathematical induction states that thrm is true for any value of parameter (for >cwhere is some constantif the following two conditions are true base casethrm holds for cand induction stepif thrm holds for then thrm holds for proving the base case is usually easytypically requiring that some small value such as be substituted for in the theorem and applying simple algebra or logic as necessary to verify the theorem proving the induction step is sometimes easyand sometimes difficult an alternative formulation of the induction step is known as strong induction the induction step for strong induction is induction stepif thrm holds for all kc < nthen thrm holds for