$(2$a$)$ Write the recurrence relation for the following function.

void SingSong$($int n$)$

$\{$

if$($n $==0)\{$

cout $<<"$No more bottles of Sarsaparilla on the wall!

$"$;

return;

$\}$

for$($int i $=0$; i $<$ n: i$++)\{$

cout $<<$ "clap $"$;

$\}$

cout $<<$ endl;

cout $<<$ n $<<"$ bottles of Sarsaparilla on the wall, $"<<$ n $<<"$ bottles of Sarsaparilla. $"$;

cout $<<$ "You take one down, pass it around. $"<<$ n$-1<<"$ bottles of Sarsaparilla on the wall.

$"$;

SingSong$($n$-1)$;

$\}$

$2$b$.)$ Use repeated substitution to show the what the recurrence looks like after two substitutions.

$2$c$.)$ Extra Credit. During substitution, don't combine any terms that look like $($n$-$i$).$ Do you notice a series like pattern? See if you can create a series in the equation, solve for it in closed form, and use it to solve for the recurrence.

$2$d$.)$ Extra Credit. Prove your equation from part $(2$c$)$ is correct using induction. $($As done in our lecture video$)$