A geometric series typically comprises of the sum of an infinite number of terms that have a constant ratio

between any two consecutive terms. In this question, you will develop a recursive algorithm to

determine the sum of a finite geometric series up to power $\text{'}$n$\text{'}($shown below$)$ such that the number of

multiplications is $\backslash$Theta $($n$)$ and the number of additions is $\backslash$Theta $($n$)$ as well.

S$($x$,$n$)=1+$ x $+$x$^2+$x$^3+...+$ x$^$n

Tasks:

$1)$ Write a pseudo code for the recursive algorithm you come up with.

$2)$ Write the recurrence relation to compute S$($x$,$ n$)$ as well as the terminating condition.

$3)$ Provide an explanation or a derivation to show that the recursive algorithm of $(1)$ uses the recurrence

relation mentioned in $(2)$ and justify that it does work as intended.

$4)$ Write the recurrence relation $($as well as the terminating condition$)$ for the number of multiplications

M$($n$)$ done in $(1-2)$ and solve the recurrence relation to show that M$($n$)=\backslash$Theta $($n$).$

$5)$ Write the recurrence relation $($as well as the terminating condition$)$ for the number of additions A$($n$)$

done in $(1-2)$ and solve the recurrence relation to show that A$($n$)=\backslash$Theta $($n$).$

Note: You will get a ZERO for the question if you provide an iterative algorithm as your solution.