Deriving Power Sums by Polynomial Interpolation

Most of us have seen these formulas: $$\sum_{i=k}^n k=1+2+\cdots+n=\dfrac{1}{2}n(n+1)\\ \sum_{i=k}^n k^2=1+4+\cdots+n^2=\dfrac{1}{6}n(n+1)(2n+1)\\ \sum_{i=k}^n k^3=1+8+\cdots+n^3=\dfrac{1}{4}n^2(n+1)^2\\ \sum_{i=k}^n k^4=1+16+\cdots+n^4=\dfrac{1}{30}n(n+1)(2n+1)(3n^2+3n-1).$$ These can be proved by mathematical induction, but we can actually derive them on our own!

We simply acknowledge the following fact: for any positive integer $p$, the power sum $\sum_{k=1}^n k^p$ can always be expressed as a polynomial $f(n)$ that has degree $p+1$ and has rational coefficients.

Let's try to derive the first and the last formula. For the first, let $f(n)=an^2+bn+c$. We have $f(1)=1,f(2)=3,f(3)=6$. We want to solve the linear system: $$a+b+c=1\\ 4a+2b+c=3\\ 9a+3b+c=6,$$ or equivalently in matrix form $$\begin{pmatrix}1&1&1\\ 4&2&1\\ 9&3&1\end{pmatrix}\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}1\\3\\6\end{pmatrix}.$$ Note that $$\begin{pmatrix}1&1&1\\ 4&2&1\\ 9&3&1\end{pmatrix}$$ is a Vandermonde matrix. Just type in vander([1 2 3])\[1;3;6] in Matlab and we have the solution: $a=1/2,b=1/2,c=0$.

For the last formula, let $f(n)=an^5+bn^4+cn^3+dn^2+en+f$. Then $f(1)=1,f(2)=17,f(3)=98,f(4)=354,f(5)=979,f(6)=2275$. Type vander([1 2 3 4 5 6]\[1;17;98;354;979;2275] in Matlab and we have $a=1/5, b=1/2, c=1/3, d=0, e=-1/30, f=0$. Finally, factor(1/5*x^5+1/2*x^4+1/3*x^3-1/30*x) gives the formula. The reader can also try to derive the formulas for $\sum_{i=k}^n k^5$ and $\sum_{i=k}^n k^6$.

Manipulations of Sums

Let $a_1,a_2,\cdots$ be any sequence of numbers. We are often interested in sums such as $a_1+\cdots+a_n$. This sum can be written more compactly using either of the following equivalent notations: $$\sum_{i=1}^n a_i\quad \text{or}\quad \sum_{1\leq i\leq n} a_i.$$ In general, if $R(i)$ is any relation involving $i$, the symbol $$\sum_{R(i)} a_i$$ means the sum of all $a_i$, where $i$ is an integer satisfying the condition $R(i)$. The letter $i$ is a dummy variable or index variable that may be renamed without changing the result.

We now discuss four important algebraic operations on sums.

1) The distributive law, for products of sums $$\bigg(\sum_{R(i)} a_i\bigg)\bigg(\sum_{S(j)} b_j\bigg)=\sum_{R(i)}\bigg(\sum_{S(j)} a_ib_j\bigg)$$ Consider for example $$\begin{align}\bigg(\sum_{i=1}^2 a_i\bigg)\bigg(\sum_{j=1}^3 b_j\bigg)&=(a_1+a_2)(b_1+b_2+b_3)\\ &=(a_1b_1+a_1b_2+a_1b_3)+(a_2b_1+a_2b_2+a_2b_3)\\ &=\sum_{i=1}^2\bigg(\sum_{j=1}^3 a_ib_j\bigg).\end{align}$$ 2) Interchanging order of summation $$\sum_{R(i)}\sum_{S(j)} a_{ij}=\sum_{S(j)}\sum_{R(i)} a_{ij}$$ For example,  $$\sum_{R(i)}\sum_{j=2}^2 a_{ij}=\sum_{R(i)}(a_{i1}+a_{i2})\\ \sum_{j=1}^2 \sum_{R(i)} a_{ij}=\sum_{R(i)} a_{i1}+\sum_{R(i)} a_{i2}.$$ This means that $$\sum_{R(i)}(b_i+c_i)=\sum_{R(i)}b_i+\sum_{R(i)}c_i,$$ where $b_i=a_{i1}$ and $c_i=a_{i2}$. This operation is very useful because we often know a simple form for $\sum_{R(i)} a_{ij}$ but not for $\sum_{S(j)} a_{ij}$. More generally, we have $$\sum_{R(i)}\sum_{S(i,j)}a_{ij}=\sum_{S'(j)}\sum_{R'(i,j)}a_{ij},$$ where $S'(j)$ is the relation 'there is an integer $i$ s.t. both $R(i)$ and $S(i,j)$ are true'; and $R'(i,j)$ is the relation 'both $R(i)$ and $S(i,j)$ are true'. For example, if the summation is $\sum_{i=1}^n\sum_{j=1}^i a_{ij}$, then $S'(j)$ is the relation 'there is an integer $i$ s.t. $1\leq i\leq n$ and $1\leq j\leq i$, namely $1\leq j\leq n$; and $R'(i,j)$ is the relation '$1\leq i\leq n$ and $1\leq j\leq i$', namely $j\leq i\leq n$. Thus, $$\sum_{i=1}^n\sum_{j=1}^i a_{ij}=\sum_{j=1}^n\sum_{i=j}^n a_{ij}.$$ 3) Change of variable
$$\sum_{R(i)} a_i=\sum_{R(j)} a_j=\sum_{R(p(j))} a_{p(j)}$$ The first equality holds because we are simply changing the dummy variable. In the second case, $p(j)$ is a function of $j$ that represents a permutation of the range. For each integer $i$ satisfying the relation $R(i)$, there is a unique integer $j$ satisfying the relation $p(j)=i$. This condition is always satisfied in cases $p(j)=c+j$ and $p(j)=c-j$, where $c$ is an integer not depending on $j$. For instance, $$\sum_{1\leq i\leq n} a_i=\sum_{1\leq i-1\leq n} a_{i-1}=\sum_{2\leq i\leq n+1} a_{i-1}.$$ Note that for infinite sums, replacing $j$ by $p(j)$ is valid iff $\sum_{R(j)}|a_j|$ exists.

4) Manipulating the domain
If $R(i)$ and $S(i)$ are arbitrary relations, we have $$\sum_{R(i)}a_i+\sum_{S(i)}a_i=\sum_{R(i)\;\text{or}\;S(i)}a_i+\sum_{R(i)\;\text{and}\;S(i)}a_i.$$ For example, $$\sum_{1\leq i\leq m}a_i+\sum_{m\leq i\leq n}a_i=\bigg(\sum_{1\leq i\leq n}a_i\bigg)+a_m,$$ assuming that $1\leq m\leq n$.

Examples from high school:
[The sum of a geometric progression] Assume that $r\neq 1,n\geq 0$. A conventional way of deriving the formula is to consider $S=a+ar+\cdots+ar^n$ and $S-rS$. $$a+ar+\cdots+ar^n\\ \underline{-)\; ar+ar^2+\cdots+ar^{n+1}}\\ a-ar^{n+1}=S(1-r)\\ \Rightarrow S=a\dfrac{1-r^{n+1}}{1-r}$$ This can be easily derived too by manipulating sums: $$\begin{align}a+ar+\cdots+ar^n&=a+\sum_{i=1}^n ar^i\\ &=a+r\sum_{i=1}^n ar^{i-1}\\ &=a+r\sum_{i=0}^{n-1} ar^i\\ &=a+r\sum_{i=0}^n ar^i-ar^{n+1}\\ &=a\dfrac{1-r^{n+1}}{1-r}\end{align}$$
[The sum of a arithmetic progression] Assume $n\geq 0$. Then $$\begin{align}a+(a+d)+\cdots+(a+nd)&=\sum_{i=0}^n (a+di)\\ &=\sum_{n-i=0}^n (a+d(n-i))\\ &=\sum_{i=0}^n (a+dn-di)\\ &=\sum_{i=0}^n (2a+dn)-\sum_{i=0}^n (a+di)\\ &=(n+1)(2a+dn)-\sum_{i=0}^n (a+di)\\ &=a(n+1)+\dfrac{1}{2}dn(n+1)\\ &=\dfrac{1}{2}(n+1)(2a+dn)\end{align}$$ Another example:
Let $$\begin{align}S&=\sum_{i=0}^n\sum_{j=0}^i a_ia_j\\ &=\sum_{j=0}^n\sum_{i=j}^n a_ia_j\\ &=\sum_{i=0}^n\sum_{j=i}^n a_ia_j \end{align}$$ Then $$\begin{align}2S&=\sum_{i=0}^n\bigg(\sum_{j=0}^i a_ia_j+\sum_{j=i}^n a_ia_j\bigg)\\ &=\sum_{i=0}^n\bigg((\sum_{j=0}^n a_ia_j)+a_ia_i\bigg)\\ &=\bigg(\sum_{i=0}^n a_i\bigg)^2+\bigg(\sum_{i=0}^n a_i^2\bigg)\end{align}$$ We have derived the identity $$\sum_{i=0}^n\sum_{j=0}^i a_ia_j=\dfrac{1}{2}\bigg(\bigg(\sum_{i=0}^n a_i\bigg)^2+\bigg(\sum_{i=0}^n a_i^2\bigg)\bigg).$$

Examples in analysis
In Riemann integration, we have the following result: Suppose $f\in \mathscr{R}[a,b]$ and $g\in \mathscr{C}([m,M])$, where $M=\sup\{f(x)\mid a\leq x\leq b\}$ and $m=\inf\{f(x)\mid a\leq x\leq b\}$. Then $g\circ f\in \mathscr{R}[a,b]$.

Idea: Consider continuous points and discontinuous points separately.

Proof: Let $\varepsilon>0$. Since $g$ is uniformly continuous on $[m,M]$, there exists $\delta>0$ s.t. $|g(x)-g(y)|<\varepsilon$ as $x,y\in [m,M]$ and $|x-y|<\delta$. Also, since $f\in \mathscr{R}[a,b]$, there exists a partition $P=\{x_0,x_1,\cdots,x_n\}$ of $[a,b]$ s.t. $U(f,P)-L(f,P)<\varepsilon \delta$. Consider $A=\{i\mid osc(f)< \delta\}$ (index w.r.t. continuous points) and $A^c=\{i\mid osc(f)\geq \delta\}$ (index w.r.t. discontinuous points). $i\in A$ does not cause much trouble. To handle $i\in A^c$, consider $$\begin{align}\sum_{i\in A^c}(x_i-x_{i-1})&=\dfrac{1}{\delta}\sum_{i\in A^c}\delta (x_i-x_{i-1})\\ &\leq \dfrac{1}{\delta}\sum_{i=1}^n(M_i(f)-m_i(f))(x_i-x_{i-1})\\ &=\dfrac{1}{\delta}(U(f,P)-L(f,P))\\ &<\varepsilon. \end{align}$$ Therefore, $$\begin{align}U(g\circ f,P)-L(g\circ f,P)&=\sum_{i=1}^n\bigg(\sup_{[x_{i-1},x_i]}(g\circ f)-\inf_{[x_{i-1},x_i]}(g\circ f)\bigg)(x_i-x_{i-1})\\ &=\sum_{i\in A}\bigg(\sup_{[x_{i-1},x_i]}(g\circ f)-\inf_{[x_{i-1},x_i]}(g\circ f)\bigg)(x_i-x_{i-1})\\&+\sum_{i\in A^c}\bigg(\sup_{[x_{i-1},x_i]}(g\circ f)-\inf_{[x_{i-1},x_i]}(g\circ f)\bigg)(x_i-x_{i-1})\\ &\leq \varepsilon \sum_{i\in A}(x_i-x_{i-1})+C\sum_{i\in A^c}(x_i-x_{i-1})\\ &\leq \varepsilon(b-a)+C\varepsilon\\ &=(b-a+C)\varepsilon,\end{align}$$ where $C=\max\{g(u)\mid m\leq u\leq M\}-\min\{g(u)\mid m\leq u\leq M\}$. It follows that $g\circ f\in \mathscr{R}[a,b]$. $\Box$

Say we want to evaluate $\sum_{n=1}^\infty \dfrac{2n-1}{2^n}$ (which is convergent by ratio test). Consider $$\begin{align}s_n&=\sum_{k=1}^n \dfrac{2k-1}{2^k}\\ &=\dfrac{1}{2}+\sum_{k=2}^n\bigg(\dfrac{2k-1}{2^k}-\dfrac{2k-3}{2^k}\bigg)+\sum_{k=2}^n \dfrac{2k-3}{2^k}\\ &=\dfrac{1}{2}+\sum_{k=2}^n\dfrac{1}{2^{k-1}}+\sum_{k=2}^n \dfrac{2k-3}{2^k}\\ &=\dfrac{1}{2}+\sum_{k=2}^n\dfrac{1}{2^{k-1}}+\sum_{k=2}^n \dfrac{2(k-1)-1}{2^{k-1+1}}\\ &=\dfrac{1}{2}+\sum_{k=2}^n\dfrac{1}{2^{k-1}}+\sum_{k=1}^{n-1} \dfrac{2k-1}{2^{k+1}}\\ &=\dfrac{1}{2}+\sum_{k=2}^n\dfrac{1}{2^{k-1}}+\dfrac{1}{2}s_n-\dfrac{2n-1}{2^n}\\ &=1+2\bigg(1-\dfrac{1}{2^{n-1}}\bigg)-\dfrac{2n-1}{2^n}\end{align}$$ As $n\to \infty$, $s_n\to 3$.

Many manipulations of sums and other formulas become significantly simpler if we use the bracket notation: $$[\text{statement}]=\begin{cases} 1,\quad \text{if the statement is true;}\\ 0,\quad \text{if the statement is false.}\end{cases}$$ Then we can write $$\sum_{R(i)} a_i=\sum_i a_i[R(i)]$$ since the terms of that infinite sums are zero when $R(i)$ is false. In fact, we have seen this expression before -- Kronecker delta symbol is a special case of bracket notation: $$\delta_{ij}=[i=j]=\begin{cases}1,\quad \text{if }i=j\\ 0,\quad \text{if }i\neq j\end{cases}.$$ With bracket notation, we can derive rule (3) from rule (1) and (2): $$\begin{align}\sum_{R(p(j))} a_{p(j)}&=\sum_j a_{p(j)}[R(p(j))]\\ &=\sum_j \sum_i a_i [R(i)][i=p(j)]\\ &=\sum_i a_i[R(i)]\sum_j [i=p(j)].\end{align}$$ If $p$ is a permutation of the range, then we are left with $\sum_i a_i [R(i)]$, which is $\sum_{R(i)} a_i$.

We can also derive rule (2): $$\sum_{i=1}^n\sum_{j=1}^i a_{ij}=\sum_{i,j} a_{ij}[1\leq i\leq n][1\leq j\leq i]=\sum_{i,j}a_{ij}[1\leq j\leq n][j\leq i\leq n]=\sum_{j=1}^n\sum_{i=j}^n a_{ij},$$ since $[1\leq j\leq n][1\leq j\leq i]=[1\leq j\leq i\leq n]=[1\leq j\leq n][j\leq i\leq n]$.

More to explore:
Möbius inversion formula
arithmetic function

Reference
illustration

Evaluate $\int_0^\pi \log(1-2a\cos x+a^2)\;dx$

From the identity $$1-a^{2n}=(1-a^2)\prod_{i=1}^{n-1}(1-2a\cos \dfrac{i\pi}{n}+a^2),\quad a\in \Bbb R$$ prove that $$\int_0^\pi \log(1-2a\cos x+a^2)\;dx=\begin{align}\begin{cases}0\quad &|a|<1\\ 2\pi\log|a|\quad &|a|>1.\end{cases}\end{align}$$

---

The identity follows from finding the roots of $\dfrac{1-a^{2n}}{1-a^2}$, whose proof is similar to this problem.

I: Elementary real analysis
$$1-a^{2n}=(1-a^2)\prod_{i=1}^{n-1}(1-2a\cos \dfrac{i\pi}{n}+a^2)\\ \dfrac{1-a^{2n}}{1-a^2}=\prod_{i=1}^{n-1}(1-2a\cos \dfrac{i\pi}{n}+a^2)\\ 1+a^2+a^4+\cdots+a^{2n-2}=\prod_{i=1}^{n-1}(1-2a\cos \dfrac{i\pi}{n}+a^2)\\ \dfrac{\pi}{n}\log(1+a^2+a^4+\cdots+a^{2n-2})=\dfrac{\pi}{n}[\log(1-2a\cos \dfrac{\pi}{n}+a^2)+\log(1-2a\cos \dfrac{2\pi}{n}+a^2)+\cdots\\+\log(1-2a\cos \dfrac{(n-1)\pi}{n}+a^2)]$$ Recall the motivation of the definition of Riemann sum: we want to approximate an area bounded by a curve by calculating areas of rectangles. Riemann sum is the sum of areas of rectangles. We partition $[0,\pi]$ into $n$ subintervals and find the sum of areas of rectangles each with width $\dfrac{\pi}{n}$ and lengths $\log(1-2a\cos \dfrac{i\pi}{n}+a^2)$ for $i=1,2,\cdots,n$. Therefore, we have $$\begin{align}\int_0^\pi \log(1-2a\cos x+a^2)\;dx&=\lim_{n\to \infty}\dfrac{\pi}{n}\sum_{i=1}^n \log(1-2a\cos \dfrac{i\pi}{n}+a^2)\\ &=\lim_{n\to \infty}\dfrac{\pi}{n}\log(1+a^2+a^4+\cdots+a^{2n-2}).\end{align}$$ When $|a|<1$, $\log(1+a^2+a^4+\cdots+a^{2n-2})=0$. It follows that the integral is $0$ when $|a|<1$. As for $|a|>1$, the trick is to make use of the case $|a|<1$. Note that $a>1$ implies that $\dfrac{1}{a}<1$: $$\lim_{n\to \infty} \dfrac{\pi}{n}\log\bigg(a^{2n-2}(\dfrac{1}{a^{2n-2}}+\dfrac{1}{a^{2n-4}}+\cdots+1)\bigg)=\lim_{n\to \infty} \dfrac{2n-2}{n}\pi \log a=2\pi\log a.$$
II: Complex analysis

More to explore
other proofs
another proof
yet another proof
Evaluating a similar integral by complex analysis methods

Wallis Formula

i) Show that for any $n\in \Bbb N$, $\int_0^{\pi/2}\sin^n x\;dx=\dfrac{n-1}{n}\int_0^{\pi/2}\sin^{n-2} x\;dx$.
ii) Show that for any $k\in \Bbb N$, $$\int_0^{\pi/2}\sin^{2k} x\;dx=\dfrac{(2k-1)(2k-3)\cdots 3\cdot 1}{(2k)(2k-2)\cdots 4\cdot 2}\dfrac{\pi}{2}=\dfrac{(2k)!}{(2^k k!)^2}\dfrac{\pi}{2}$$ and $$\int_0^{\pi/2}\sin^{2k+1} x\;dx=\dfrac{2k(2k-2)\cdots 4\cdot 2}{(2k+1)(2k-1)\cdots 3\cdot 1}=\dfrac{(2^k k!)^2}{(2k+1)!}.$$ iii) For $k\in \Bbb N$, let $$\mu_k=\dfrac{\int_0^{\pi/2}\sin^{2k} x\;dx}{\int_0^{\pi/2}\sin^{2k+1} x\;dx}.$$ Show that $1\leq \mu_k\leq \dfrac{2k+1}{2k}$ for each $k\in \Bbb N$ and consequently that $\mu_k\to 1$ as $k\to \infty$. Deduce that $$\sqrt{\pi}=\lim_{k\to \infty} \dfrac{(k!)^2 2^{2k}}{(2k)!\sqrt{k}}.$$ Thus $\pi\sim \dfrac{(k!)^4 2^{4k}}{((2k)!)^2 k}$. (Hint: $\sin^{2k+1}x\leq \sin^{2k}x\leq \sin^{2k-1}x$ for all $x\in[0,\pi/2]$.)

---

i) $$\begin{align}\int_0^{\pi/2}\sin^n x\;dx&=-\int_0^{\pi/2}\sin^{n-1} x\;d(\cos x)\\ &=-\sin^{n-1}\cos x\bigg|_0^{\pi/2}+(n-1)\int_0^{\pi/2}\cos^2 x\sin^{n-2} x\;dx\\ &=0+(n-1)\int_0^{\pi/2}\sin^{n-2} x\;dx-(n-1)\int_0^{\pi/2}\sin^n x\;dx\\ \Rightarrow \int_0^{\pi/2}\sin^n x\;dx&=\dfrac{n-1}{n}\int_0^{\pi/2}\sin^{n-2} x\;dx \end{align}$$ ii) $$\begin{align} \int_0^{\pi/2}\sin^{2k} x\;dx&=\dfrac{2k-1}{2k}\int_0^{\pi/2}\sin^{2k-2} x\;dx\\ &=\dfrac{2k-1}{2k}\dfrac{2k-3}{2k}\int_0^{\pi/2}\sin^{2k-4} x\;dx\\ &=\dfrac{2k-1}{2k}\dfrac{2k-3}{2k}\cdots \int_0^{\pi/2}\sin^4 x\;dx\\ &=\dfrac{2k-1}{2k}\dfrac{2k-3}{2k}\cdots \dfrac{3}{4} \int_0^{\pi/2}\sin^2 x\;dx\\ &=\dfrac{2k-1}{2k}\dfrac{2k-3}{2k}\cdots \dfrac{3}{4} \dfrac{1}{2}\int_0^{\pi/2}\sin^0 x\;dx\\\\ &=\dfrac{(2k-1)(2k-3)\cdots 3\cdot 1}{(2k)(2k-2)\cdots 4\cdot 2}\dfrac{\pi}{2}\\ &=\dfrac{(2k)(2k-1)(2k-2)(2k-3)\cdots 3\cdot 2\cdot 1}{[(2k)(2k-2)\cdots 4\cdot 2]^2}\dfrac{\pi}{2}\\ &=\dfrac{(2k)!}{(2^k\cdot [k(k-1)\cdots 2\cdot 1])^2}\dfrac{\pi}{2}\\ &=\dfrac{(2k)!}{(2^k k!)^2}\dfrac{\pi}{2} \end{align}$$ The other case is similar.
Question: How come the integral of 'odd sine function' is the 'reciprocal' of that of 'even sine function'?

iii) It is simple to prove the claim with the hint (which is true because $\sin x\leq 1$ when $x\in [0,\pi/2]$). For all $x\in[0,\pi/2]$, $$\sin^{2k+1}x\leq \sin^{2k}x\leq \sin^{2k-1}x\\  \int_0^{\pi/2}\sin^{2k+1}x\;dx\leq \int_0^{\pi/2}\sin^{2k}x\;dx\leq \int_0^{\pi/2}\sin^{2k-1}x\;dx\\ \dfrac{\int_0^{\pi/2}\sin^{2k+1}x\;dx}{\int_0^{\pi/2}\sin^{2k+1}x\;dx}\leq \dfrac{\int_0^{\pi/2}\sin^{2k}x\;dx}{\int_0^{\pi/2}\sin^{2k+1}x\;dx}\leq \dfrac{\int_0^{\pi/2}\sin^{2k-1}x\;dx}{\int_0^{\pi/2}\sin^{2k+1}x\;dx}\\ 1\leq \mu_k\leq \dfrac{\int_0^{\pi/2}\sin^{2k-1}x\;dx}{\int_0^{\pi/2}\sin^{2k+1}x\;dx}$$ We have $\dfrac{\int_0^{\pi/2}\sin^{2k-1}x\;dx}{\int_0^{\pi/2}\sin^{2k+1}x\;dx}=\dfrac{[2^{k-1}(k-1)!]^2}{(2k-1)!}\dfrac{(2k+1)!}{(2^k k!)^2}=\dfrac{(2k+1)2k}{4k^2}=\dfrac{2k+1}{2k}$, hence the claim.

By sandwich theorem, since $\lim_{k\to \infty} \dfrac{2k+1}{2k}=1$, we have $\mu_k\to 1$ as $k\to \infty$. But $\mu_k\to 1$ implies $\sqrt{\mu_k}\to 1$.
Question: Why does $\mu_k$ tend to $1$ intuitively?
We can look at the graphs of powers of $\sin x$. When the powers are close to each other, their graphs are very similar. That's why the ratio of the two integrals tends to $1$.

Now, $$\mu_k=\dfrac{\pi}{2}\dfrac{(2k)!(2k+1)!}{(2^k k!)^4}\\ \sqrt{\mu_k}=\dfrac{\sqrt{\pi}}{\sqrt{2}}\dfrac{\sqrt{(2k)!(2k+1)!}}{(2^k k!)^2}=\sqrt{\pi}\dfrac{\sqrt{2k+1}}{\sqrt{2}}\dfrac{(2k)!}{(2^k k!)^2} \to 1.$$ It follows that $$\sqrt{\pi}=\lim_{k\to \infty} \dfrac{(2^k k!)^2}{(2k)!\sqrt{k}}$$ For the approximation of $\pi$, just take the square of the limit.

Wallis Formula is one of the many formulas that approximates $\pi$. There are other proofs of this formula. See the notes by Steven R. Dunbar.

More to explore
notes by Steven R. Dunbar
math fun facts
notes by Ben Lynn
paper

Interesting reults related to $a+b-ab$

Abstract Algebra

Consider a unital ring $R$ with identity $1$. If $a\in R$ has a right inverse $b$, then writing $a=1-z$ and $b=1-w$, we have $$1=ab=(1-z)(1-w)=1-z-w-zw.$$ The condition on $z$ and $w$ is thus $$z+w-zw=0.$$ Since this condition does not involve the identity, we can use it for an arbitrary ring.

Definitions: Let $R$ be an arbitrary ring. An element $z\in R$ is called right (left) quasi-regular if there exists an element $w$ in $R$ such that $z+w-zw=0$ $(z+w-wz=0)$. The element $w$ is called a right (left) quasi-inverse of $z$.
Let $R$ be a unital ring with identity $1$. Then $z\in R$ is called right (left) quasi-regular if  $1-z$ has a right (left) inverse.
If $z$ is both left and right quasi-regular, then $z$ is quasi-regular.

Let $R$ be a commutative ring and define a binary composition (known as the circle composition) in $R$ by $$a\cdot b=a+b-ab.$$ One can check that $(R,\cdot)$ is associative and forms a semigroup. Here in $(R,\cdot)$, the identity is not $1$, but $0$: $a\cdot 0=0=0\cdot a$. The set of quasi-regular elements $Q$ are the elements $a$ s.t. $a\cdot b=0$ and $b\cdot a=0$, namely they are the units of $(R,\cdot)$. We know that the set of units forms a group. It follows that the set of quasi-regular elements together with the circle composition $(Q,\cdot)$ is a group.

Claim: The mapping $$\phi:Q\to U(R)\\ a\mapsto 1-a$$ is an isomorphism of $Q$ onto $U(R)$. [$U(R)$ denotes the group of units of $R$.]
Proof: It is clear that the map is a bijection with inverse $a\mapsto 1-a$. ($1-a\mapsto 1-(1-a)=a$)
$\phi(a\cdot b)=\phi(a+b-ab)=1-a-b+ab=(1-a)(1-b)=\phi(a)\phi(b)$. $\Box$

Claim: Any nilpotent element is quasi-regular.
Proof: If $r^n=0$, and $s=1+r+r^2+\cdots+r^{n-1}$, then $(1-r)s=s(1-r)=1$, so nilpotent elements are quasi-regular. $\Box$

Corollary: If $r$ is nilpotent, then both $1+r$ and $1-r$ are units. [For $1+r$, take $s=\sum_{i=0}^{n-1} (-1)^i r^i$]

Logic

Consider a truth function s.t. $T(A)=1$ if the statement $A$ is true; $T(A)=0$ if $A$ is false. To generalise this, let $T(A)=a$, $T(B)=b$. $$T(A\cap B)=a+b-ab\\ T(A\cup B)=ab$$ The use of $T$ allows one to reduce logical problems to algebraic equations. For more information, one can refer to a text on Boolean algebra.

There are similar results of characteristic functions and sets.
$$\chi_{A\cup B}=\chi_A+\chi_B-\chi_{A\cap B}\\ \chi_{A\cap B}=\chi_A\chi_B\\ \chi_{A\triangle B}=\chi_A+\chi_B-2\chi_{A\cap B}\\ \\ |A\cup B|=|A|+|B|-|A\cap B|$$

More to explore:
idempotents
orthogonal idempotents
Jacobson radical