Evaluate Triple Sum

Relevant wiki: Prime counting function

This triple sum counts up the number of prime numbers up to $2016$ , which works out to $305$ .

First, we start with the statement, which will be proven later

$\displaystyle\sum _{ k=0 }^{ n }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \left( -1 \right) }^{ n+k }{ \left( m+k \right) }^{ j } \right)}$ $=0$ , if $0 \le j<n$ , $\;\; n!$ , if $j=n$ , for all integer $n, m>0$

from which we can state, letting $m=n$ arbitrarily

$\displaystyle \sum _{ j=0 }^{ q }{\displaystyle \sum _{ k=0 }^{ n }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \left( -1 \right) }^{ n+k }{ \left( n+k \right) }^{ j } \right) } }$ $=0$ , if $0 \le q<n$ , $\;\;n!$ , if $q=n$

again from which we can state, reversing order of summation and dividing by $n!$

$\displaystyle \sum _{ k=0 }^{ n }{\displaystyle \sum _{ j=0 }^{ q }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \dfrac { {\left(- 1 \right) }^{ n+k }{ \left( n+k \right) }^{ j } }{ n! } } \right) } }$ $=0$ , if $0 \le q<n, \;\;1$ , if $q=n$

Now from number theory (at least not yet proven otherwise)

$\phi \left( n \right) +1=n$

only if $n$ is prime, otherwise

$\phi \left( n \right) +1<n$

so that from above, we can state

$\displaystyle \sum _{ k=0 }^{ n }{\displaystyle \sum _{ j=0 }^{ \phi \left( n \right) +1 }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \dfrac { { \left( -1 \right) }^{ n+k }{ \left( n+k \right) }^{ j } }{ \left( \phi \left( n \right) +1 \right) ! } } \right) } }$ $=0$ , if $n=$ not prime, $\;\;1$ , if $n=$ prime

from which we can do the third and final summation

$\displaystyle \sum _{ n=2 }^{ x }{\displaystyle \sum _{ k=0 }^{ n }{\displaystyle \sum _{ j=0 }^{ \phi \left( n \right) +1 }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \frac { { \left( -1 \right) }^{ n+k }{ \left( n+k \right) }^{ j } }{ \left( \phi \left( n \right) +1 \right) ! } } \right) } } } =\pi \left( x \right)$

where $\pi \left( x \right)$ is the Prime Counting function, which counts the number of primes equal to $x$ or less. Hardly the most efficient formula as a Prime Counting function, but it still works as one.

Additional notes:

If you are still wondering about

$\displaystyle\sum _{ k=0 }^{ n }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \left( -1 \right) }^{ n+k }{ \left( m+k \right) }^{ j } \right)}$ $=0$ , if $0 \le j<n$ , $\;\; n!$ , if $j=n$ , for all integer $n,m>0$

restate it as follows

$\displaystyle \sum _{ k=0 }^{ n }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \left( -1 \right) }^{ n+k }\sum _{ i=0 }^{ j }{ \left( \left( \begin{matrix} j \\ i \end{matrix} \right) { \left( m-1 \right) }^{ i }{ \left( k+1 \right) }^{ j-i } \right) } \right) }$ $=0$ , if $0 \le j<n$ , $\;\; n!$ , if $j=n$ , for all integer $n, m>0$ or, reversing order of sum

$\displaystyle \sum _{ i=0 }^{ j }{ \left( \left( \begin{matrix} j \\ i \end{matrix} \right) { \left( m-1 \right) }^{ i }\sum _{ k=0 }^{ n }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \left( -1 \right) }^{ n+k }{ \left( k+1 \right) }^{ j-i } \right) } \right) }$ $=0$ , if $0 \le j<n$ , $\;\; n!$ , if $j=n$ , for all integer $n, m>0$

which holds true for all integer $n, m>0$ if

$\displaystyle \sum _{ k=0 }^{ n }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \left( -1 \right) }^{ n+k }{ \left( k+1 \right) }^{ j } \right) }$ $= 0$ , if $0 \le j<n$ , $\;\; n!$ , if $j=n$ , for all integer $n>0$

This can be restated as

$\displaystyle \sum _{ k=0 }^{ n }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \left( -1 \right) }^{ n+k }{ \left( k+1 \right) \left( k+1 \right) }^{ j-1 } \right) }$ $= 0$ , if $0 \le j<n$ , $\;\; n!$ , if $j=n$

and since

$\displaystyle \sum _{ k=0 }^{ n }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \left( -1 \right) }^{ n+k }{ \left( 1 \right) \left( k+1 \right) }^{ j-1 } \right) }$ $= 0$ , if $1 \le j<n$ , $\;\; n!$ , if $j=n$

we have, after the difference is divided by $n$ (with $k=0$ yielding the trivial value of $0$ )

$\displaystyle \sum _{ k=1 }^{ n }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \left( -1 \right) }^{ n+k }{ \left( \frac { k }{ n } \right) { \left( k+1 \right) }^{ j-1 } } \right) }$ $= 0$ , if $1 \le j<n$ , $\;\; n!$ , if $j=n$

or

$\displaystyle \sum _{ k=1 }^{ n }{ \left( \left( \begin{matrix} n-1 \\ k-1 \end{matrix} \right) { \left( -1 \right) }^{ n+k }{ { \left( k+1 \right) }^{ j-1 } } \right) }$ $= 0$ , if $1 \le j<n$ , $\;\; n!$ , if $j=n$

which is back to where we were, but with $n$ decreased by $1$

$\displaystyle \sum _{ k=0 }^{ n }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \left( -1 \right) }^{ n+k }{ { \left( k+1 \right) }^{ j } } \right) }$ $= 0$ , if $0 \le j<n$ , $\;\; n!$ , if $j=n$ , for all integer $n>0$

Through induction, we reach the trivial case where $n=1$ and compute the values directly for $j=0$ and $j=1$ .

$\displaystyle \sum _{ k=0 }^{ 1 }{ \left( \left( \begin{matrix} n \\ k \end{matrix} \right) { \left( -1 \right) }^{ n+k }{ { \left( k+1 \right) }^{ j } } \right) }$ $= 0$ , for $j=0$ , and $1$ , for $j=1$ .

The proof in more correct form should start at the bottom and through induction prove for all $n>0$ by taking the steps in reverse order.