sec summations and recurrences from this definition we see that the first seven numbers of the fibonacci sequence are and notice that this definition contains two partsthe general definition for fib(nand the base cases for fib( and fib( likewisethe definition for factorial contains recursive part and base cases recurrence relations are often used to model the cost of recursive functions for examplethe number of multiplications required by function fact of section for an input of size will be zero when or (the base cases)and it will be one plus the cost of calling fact on value of this can be defined using the following recurrencet(nt( for ( ( as with summationswe typically wish to replace the recurrence relation with closed-form solution one approach is to expand the recurrence by replacing any occurrences of on the right-hand side with its definition example if we expand the recurrence (nt( we get (nt( ( ( we can expand the recurrence as many steps as we likebut the goal is to detect some pattern that will permit us to rewrite the recurrence in terms of summation in this examplewe might notice that ( ( ( and if we expand the recurrence againwe get (nt( ( ( which generalizes to the pattern (nt( ii we might conclude that (nt( ( )( (