Relation between Simpson's Rule, Trapezoid Rule and Midpoint Rule I am studying numerical approximation and verifying $S_{2n} = \frac{1}{3}\left(T_n +2 M_n\right)$. ($S_n$ refers to Simpson's Rule approximation, $T_n$ refers to Trapezoid Rule approximation and $M_n$ refers to Midpoint Rule approximation) I listed all the formulas and manipulated the equations, but I have no idea how $2n$ numbers come out at the left side while only $n$ numbers at the right side.
 A: For the Trapezoidal Rule, you actually use $n+1$ points. For example, in the simple case where you are integrating $f(x)$ from $0$ to $1$, and you want $T_4$, you  evaluate $f$ at the points $0/4$, $1/4$, $2/4$, $3/4$, and $4/4$.  It is $n+1$ points because we use the endpoints.  
For the Midpoint Rule, you use $n$ points, but these are not the same points as for the Trapezoidal Rule. They are the midpoints of our intervals. So in the example discussed above, for $M_4$ you would be evaluating $f$ at $1/8$, $3/8$, $5/8$, and $7/8$.
The Simpson Rule $S_{2n}$ uses evaluation of $f$ at $2n+1$ points. If for example $n=4$, then you are dividing the interval into $8$ subintervals. With $n=4$ and the interval $[0,1]$, you would be using the points $0/8$, $1/8$, $2/8$, $3/8$, $4/8$, $5/8$, $6/8$, $7/8$, and $8/8$. 
Note that $1/8$, $3/8$, $5/8$ and $7/8$ are the points that were used for $M_4$. The points $0/8$, $2/8$, $4/8$, $6/8$, and $8/8$ are just $0/4$, $1/4$, $2/4$, $3/4$, and $4/4$, exactly the points that were used for $T_4$.   
A more abstract summary: $T_n$ uses $n+1$ points, and $M_n$ uses $n$ points. But the $n$ points used by $M_n$ are completely different from the points used for $T_n$. So altogether, $T_n$ and $M_n$ carry information about function evaluation at $2n+1$ points, which is exactly what $S_{2n}$ does. 
I have not written out a proof of the formula, only tried to deal with your discomfort with the $2n$ on one side and  $n$'s on the other. The formula is not hard to verify. Let's do it explicitly for $n=4$. Write down, say for the interval $[0,1]$, what $T_4$ is. 
We have
$$T_4=\frac{1}{8}(f(0)+2f(1/4)+2f(1/2)+2f(3/4)+f(1)).$$
Now write down $M_4$:
$$M_4=\frac{1}{4}(f(1/8)+f(3/8)+f(5/8)+f(7/8)).$$
Now calculate $T_4+2M_4$. It is convenient for the addition to make sure that $M_4$ has denominator $8$, so write $2M_4$ as $\frac{1}{8}(4f(1/8)+4f(3/8)+4f(5/8)+4f(7/8))$, and add. Divide by $3$ and you will get the expression you would get in $S_{8}$. The same method works in general. 
A: For given $n\in{\mathbb N}$ each of $S_{2n}$, $T_n$ and $M_n$ are one number, and each of these three numbers claim to be an approximation to the number
$$\int_a^b f(x)\ dx\ .$$
They are arrived at as follows: The interval $[a,b]$ is divided into $n$ equal parts $[x_{n-1},x_n]$ of length ${b-a\over n}$. When $f$ is interpolated by a piecewise linear function $g$ such that $g(x_i)=f(x_i)$ $\ (0\leq i\leq n)$ then
$$T_n:=\int_a^b g(x)\ dx={b-a\over n}\bigl({1\over2}(f(a)+f(b))+\sum_{k=1}^{n-1} f(x_k)\bigr)\ .$$
For $M_n$ the function $f$ is replaced by a function $h$ which is constant on each subinterval $[x_{k-1},x_k]$, and the value of $h$ on this interval is defined to be $f\Bigl({x_{k-1}+x_k\over2}\Bigr)$. This leads to
$$M_n=\int_a^b h(x)\ dx={b-a\over n}\sum_{k=1}^nf\Bigl({x_{k-1}+x_k\over2}\Bigr)\ .$$
Note that the $n$ places where $f(x)$ has to be computed to obtain $M_n$ are different from the $n+1$ places where $f(x)$ has to be computed to obtain $T_n$.
Finally, the Simpson value $S_{2n}$ is defined as
$$S_{2n}:={1\over3}(T_n+2M_n)\ .$$
For $S_{2n}$ you have to evaluate $f$ at $2n+1$ different $x$'s; in return you get a much better approximation than with $M_n$ and $T_n$. One arrives at this formula by replacing $f$ in each subinterval $[x_{k-1},x_k]$ by a quadratic function having the same value as $f$ in the points $x_{k-1}$, ${x_{k-1}+x_k\over2}$ and $x_k$.
