Consider a given modification of the function RANDOM(n) below and give a recursive equation for the three cases considered in the class.

Function RANDOM(n)

1 If n=1 then

1.1 Return (1)

1.2 Else

2.1 Assign x=0 with probability , or

2.2 Assign x=1 with probability , or

2.3 Assign x=2 with probability ,

3 If x=0 then

3.1 Return (RANDOM(n) + RANDOM(n-1))

3.2 End-if

4 If x=1 then

4.1 Return (RANDOM(n-1) + RANDOM(n-2) + 3)

4.2 End-if

5 If x=2 then

5.1 Return (RANDOM(n) + RANDOM(n-2) + 3)

5.2 End-if

6 End-if

7 end-RANDOM