CAS CS 131 - Combinatorial StructuresSpring 2011Problem Set #3 (Sums)Out: Thursday, February 17Due: Thursday, February 24NO LATE SUBMISSIONS WILL BE ACCEPTEDTo be completed individually.1. You had previously proved by induction that, for any natural number n ≥ 1,12+ 22+ 32+ · · · + n2=n(n+1)(2n+1)6.Use this result to evaluate the following sum.2nXk=n+1k22. You had previously proved by induction that, for all real values r 6= 1:1 + r + r2+ r3+ · · · + rn=1−rn+11−r, for any natural number n ≥ 0.Use this result to evaluate the following sum.nXi=0mXj=03i+j3. Tommy the Monster is a financial service provider who offers loans on the following terms.• Tommy loans a client m dollars in the morning. This puts the client m dollars in debtto Tommy.• Each evening, Tommy first charges a “service fee”, which increases the client’s debt byf dollars, and then Tommy charges interest, which multiplies the debt by a factor of p.For example, if Tommy’s interest rate were a modest 5% per day, then p would be 1.05.(a) What is the client’s debt at the end of the first day?(b) What is the client’s debt at the end of the second day?(c) Write a formula for the client’s debt after d days and find an equivalent closed form.4. You have seen this so-called “perturbation” method to evaluate a geometric sum:S = 1 + z + z2+ · · · + znzS = z + z2+ · · · + zn+ zn+1S − zS = 1 − zn+1S =1 − zn+11 − z1Use the same approach to find a closed-form expression for this sum:T = z + 2z2+ 3z3+ · · · + nzn5. Find a closed-form expression equal to the following sum. Show your work.nXj=1∞Xi=0j5/31