Question 6 Those of you who come to class will remember that

Question 6: Those of you who come to class will remember that Elisa Kazan loves to drink cider. After a week of bossing the Vice-Presidents around, Elisa goes to the pub and runs the following recursive algorithm, which takes as input an integer n 2 0: Algorithm ELIsaGOEsToTHEPUB(n): ifn=0 then drink one bottle of cider else for k = 0 to n-1 do ELISAGOESTOTHePUB(k); drink one bottle of cider endfor endif For n 2 0, let C(n) be the number of bottles of cider that Elisa drinks when running algorithm ELIsAGOESToTHEPUB(n) Prove that for every integer n 2 1, C(n) 3-2\"-1 -1. Hint: 1+2 +22 +23 ++2-2211.

Solution

C(0) = 1
C(1) = C(0) + 1 = 2
C(2) = C(0) + C(1) + 2
C(3) = C(0) + C(1) + C(2) + 3
.
.
.
.
C(n) = C(0) + C(1) + C(2) +....... + C(n-1) + n

Let us assume C(n) = 3*2^n-1 - 1

Now, C(n+1) = C(0) + C(1) + C(2) + ...... C(n) + n + 1

= 1 + 3*(2^0 + 2^1 +.......2^n-1) - (n) + n + 1

= 1 + 3*(1-2ⁿ)/-1 + 1

= 3*2ⁿ + 2 - 3

= 3*2ⁿ - 1

Hence, by induction, C(n) = 3*2^n-1 - 1