then replace cstamp with three cstamps if notthen the makeup must have included at least two cstamps (because it is at least of size and contains only cstampsin this casereplace two of the cstamps with single cstamp in either casewe now have value of made up of cand cstamps thusby mathematical inductionthe theorem is correct example here is an example using strong induction theorem for is divisible by some prime number prooffor the base casechoose is divisible by the prime number the induction hypothesis is that any value < nis divisible by some prime number there are now two cases to consider when proving the theorem for if is prime numberthen is divisible by itself if is not prime numberthen for and bboth integers less than but greater than the induction hypothesis tells us that is divisible by some prime number that same prime number must also divide thusby mathematical inductionthe theorem is correct our next example of mathematical induction proves theorem from geometry it also illustrates standard technique of induction proof where we take objects and remove some object to use the induction hypothesis example define two-coloring for set of regions as way of assigning one of two colors to each region such that no two regions sharing side have the same color for examplea chessboard is two-colored figure shows two-coloring for the plane with three lines we will assume that the two colors to be used are black and white theorem the set of regions formed by infinite lines in the plane can be two-colored proofconsider the base case of single infinite line in the plane this line splits the plane into two regions one region can be colored black and the other white to get valid two-coloring the induction hypothesis is that the set of regions formed by infinite lines can be two-colored to prove the theorem for nconsider the set of regions formed by the lines remaining when any one of the lines is removed by the induction hypothesisthis set of regions can be two-colored nowput the nth line back this splits the plane into two half-planeseach of which (independentlyhas valid two-coloring inherited from the two-coloring of the plane with