Problem $3$: Below are two functions that calculates the sum of the first n

integers using python. In other words, sum$($n$)=1+2+3+...+$ n$.$

def sum$1($n$)$:

if $($n $==1)$:

return $1$

else:

return n $+$ sum$1($n$-1)$

def sum$2($n$)$:

return n$*($n$+1)/2$

Answer the questions below:

$($a$)$ Choose $5$ different numbers for n$.$ Verify that sum$1($n$)$ equals sum$2($n$)$ for

these $5$ numbers.

$($b$)$ Which of these two functions do you think is generally more efficient for

n $>100.$ Why do you think this is so$?$

$($c$)$ Do you think sum$1(1)$ or sum$2(1)$ is more efficient? Why?

$($d$)$ What happens if you call sum$1(0)?$

$($e$)$ Let$$s define the open sentance:

P$($n$)$: sum$1($n$)$ is a valid calculation.

i$.$ What is the smallest n in N such that P$($n$)$ is true? Let$$s label this

case P$($b$),$ where b is this smallest such number. In other words,

what is b$?$

ii$.$ What is P$($b$+1)?$ What is P$($b$+2)?$ What is P$($b$+3)?$ Are these also

true statements?

iii. Is the following statement true or false: P$($b$)$ P$($b$+1)?$

iv$.$ Assume you could use sum$2($n$)$ to validate whether sum$1($n$)$ is correct

for large number of n$.$ How would you rewrite the open statement

P$($n$)?$

v$.$ Can you rewrite sum$1($n$)$ so that it calls sum$2($n$)?$

$4$