$a_n=2a_{n-1}+3$

$a_1=4$

Prove by induction on $n$ that the following pseudocode on input integer $n$ returns $a_n,$ for

all $n1.$ As usual, clearly define the statement $P(n)$ and show each of the parts of a proof

by induction. Also, be sure to identify where you use the induction hypothesis.

Algorithm CalculateSequence $(n)$

Input: integer $n1$

Output: $a_n($where the sequence $a_n$ is defined above$)$

if $n=1$ then $\frac{,}{\frac{?}{?}}$ line $1$

return $4\frac{,}{\frac{?}{?}}$ line $2$

else

return $2**$ CalculateSequence $(n-1)+3\frac{,}{\frac{?}{?}}$ line $3$