chap mathematical preliminaries takes care of the rest " - ( ( = = ( ) thusby mathematical inductionpn = ( example this example shows how we can use induction to prove that proposed closed-form solution for recurrence relation is correct theorem the recurrence relation (nt( - )+ ( has closed-form solution (nn proofto prove the base casewe observe that ( the induction hypothesis is that ( combining the definition of the recurrence with the induction hypothesiswe see immediately that (nt( for thuswe have proved the theorem correct by mathematical induction example this example uses induction without involving summations or other equations it also illustrates more flexible use of base cases theorem cand cstamps can be used to form any value (for values > proofthe theorem defines the problem for values > because it does not hold for the values and using as the base casea value of ccan be made from two cstamps the induction hypothesis is that value of can be made from some combination of cand cstamps we now use the induction hypothesis to show how to get the value from cand cstamps either the makeup for value includes cstampor it does not if so