computational complexity copy operations the third append requires three copy operations sowe have the following number of list elements being copied ** = in mathematics we can express this sum with summation symbol ( this is the mathematical way of expressing the sum of the first integers butwhat is this equal toit turns out with little workwe can find that the following is true ii= ( we can prove this is true using proof technique from mathematics called mathematical induction there are couple of variations of mathematical induction we'll use what is called weak induction to prove this when proving something using induction you are really constructing meta-proof meta-proof is set of steps that you can repeat over and over again to find your desired result the power of induction is that once we have constructed the meta-proofwe have proved that the result is true for all possible values of we want to prove that the formula given above is valid for all to do this we first show it is true for simple value of in our case we'll pick as our value of in that case we have the following = = ( this is surely true this step is called the base case of the inductive proof every proof by induction must have base case and it is usually trivial the next step is to create the meta-proof this meta-proof is called the inductive case when forming the inductive case we get to assume that the formula holds for all valuesmwhere is less than this is called strong induction in weak induction we get to assume that the formula is valid for - and we want to show that it is valid for we'll use weak induction in this problem to finish our proof againthis step helps us form set of steps that we can apply over and over again to get from our base case to whatever value of we need to find to begin we will make note of the following - + ii= = this is true by the definition of summation but now we have sum that goes to and weak induction says that we know the equation is valid for this is called the inductive hypothesis since it holds for we know the following is true we get this by substituting everyplace that we see an in the original formula - = ( ) this copy belongs to 'acha