Problem $6.$ Gaussian Location

Historical background $($not necessary to solve the problem, but interesting$)$:

Carl Friedrich Gauss was a German mathematician born in the $18$th century, who is credited for several key ideas in mathematics that you're familiar with. For one, Gaussian elimination $($also known as row reduction$)$ in linear algebra is named after him. He's also credited for being the first person to my error $-$ he did so to build a model to predict the locations of planets in the night sky

Perhaps the most famous story involving Gauss is one from when he was just a child. His teacher, supposedly, asked him to add the integers from $1$ through $100,$ expecting it to take him a while. However, within just a few seconds, he gave the answer $5050.20-$style algorithmic problem efficiently.

The actual problem:

Here, we'll solve the "missing value problem." Suppose vals is a list of length $n-1,$ containing the integers from $1$ to $n,$ inclusive, with no duplicates and in unsorted order, but with exactly $1$ value missing. Your job is to write a function that finds the missing integer in vals. For example, if vals $=[1,2,5,3],$ the missing integer is $4.$

Parts $($a$)$ and $($c$)$ of this problem will require you to write code in this supplementary Jupyter Notebook. The code that you write in that notebook is autograded, both using public test cases that you can see in the notebook and hidden test cases that will only be run after you submit on Gradescope.

To submit your homework, in addition to submitting your answers PDF to the Homework $1$ assignment on Gradescope, also submit hw$01-$code.ipynb to the Homework $1,$ Problems $6($a$)$ and $6($c$)$ autograder on Gradescope and wait until you see all public test cases pass!

a$)6\mathrm{.}6$ In the linked supplementary notebook, complete the implementation of the function missing$-$value$\_$naive There's nothing you need to include in your answers PDF for this part.

b$)6\mathrm{.}6.$ Your implementation of missing$\_$value$\_$naive didn't need to be particularly efficient. To make our solution to the missing value problem more efficient, we'll use the fact that the missing value is the difference between the sum we'd expect if none of the values were missing, and the sum of the values we actually have. For example, if vals $=[1,2,5,3],$ then $n=5,$ so the sum we'd expect is $1+2+3+4+5=15,$ and so the missing value is $(1+2+3+4+5)-(1+2+5+3)=15-11=4.$ To find the expected sum, instead of using a for$-$loop or something like sum $($range$(1,$ n$+1)),$ we can turn to Gauss to make things even faster. Let's look at how he quickly derived that $1+2+$dots$+99+100=5050.$ Your job will then be to generalize what he did to $1+2+$dots$+n,$ and find a formula for the sum of the first $n$ positive integers.

Let $S_{100}=1+2+$dots$+99+100.$ Gauss wrote out $S_{100}$ in two different ways:

$S_{100}=1+2+3+$cdots$+98+99+100$

$S_{100}=100+99+98+$cdots$+3+2+1$

Then, he noticed that each vertical pair of terms $-1$ and $100,2$ and $99,100$ and $1-$ each summed to $101.$ By adding the two lines above, he saw:

$2S_{100}=101+101+101+$dots$+101+101+101$

Since there were $100$ terms in each of the original equations for $S_{100},$ there were $100$ terms equal to $101$ in the equation above for $2S_{100}.$ This let him solve for $S_{100}$ :

$5$

$2S_{100}=101+101+101+$dots$+101+101+101$

$2S_{100}=100*101$

$S_{100}=\frac{100*101}{2}=50*101=5050$

Now, it's your turn. Let $S_n=1+2+$dots$+n.$ Find a closed$-$form expression for $S_n,$ for any integer $n1,$ and show your work. Your answer will be an arithmetic expression involving $n$; for example, an incorrect answer in the correct format could be $4n^3.$

Hint: This problem may seem daunting at first, but most of the work has already been done for you. What you need to do is repeat Gauss' work, but with an arbitrary integer $n$ instead of $100.$ When you expand $S_n$ twice, the way that Gauss expanded $S_{100}$ twice, what is the sum of each vertical pair of terms? How many such terms are there? Verify that your answer is correct by testing it out on $1+2,1+2+3,1+2+3+4,$ etc.

c$)6\mathrm{.}6$ In the linked supplementary notebook, complete the implementation of the function missing$-$value fast There's nothing you need to include in your answers PDF for this