true for nthen (nis true the combination of these two pieces completes the justification by induction proposition consider the fibonacci function ( )where we define ( ( and (nf( ( for (see section we claim thatf( justificationwe will show our claim is right by induction base cases( < ( and ( induction step( suppose our claim is true for consider (nsince (nf( ( moreoversince < and nwe can apply the inductive assumption (sometimes called the "inductive hypothesis"to imply that ( since - - - - let us do another inductive argumentthis time for fact we have seen before proposition (which is the same as proposition justificationwe will justify this equality by induction base casen trivialfor ( )/ if induction stepn > assume the claim is true for consider by the induction hypothesisthen which we can simplify as ( ) / / / ( )/