sec recurrence relations useful in the first term remember that the goal of such manipulations is to give us an equation that relates (nto something without recursive calls for large nwe also observe thatf (nf (nf ( ( ( ( as gets big this comes from multiplying ( )/ ( by ( )/ ( and rearranging if existsthen using the quadratic equationthe only solution greater than one is this expression also has the name ph what does this say about the growth rate of the fibonacci sequenceit is exponentialwith (nth(phn more preciselyf (nconverges to phn ( ph) expanding recurrences estimating bounds is effective if you only need an approximation to the answer more precise techniques are required to find an exact solution one such technique is called expanding the recurrence in this methodthe smaller terms on the right side of the equation are in turn replaced by their definition this is the expanding step these terms are again expandedand so onuntil full series with no recurrence results this yields summationand techniques for solving summations can then be used couple of simple expansions were shown in section more complex example is given below example find the solution for ( ( / ( for simplicity we assume that is power of twoso we will rewrite it as this recurrence can be expanded as followst( ( /