Summation over k of Floor of k over 2
Jump to navigation
Jump to search
Theorem
- $\ds \sum_{k \mathop = 1}^n \floor {\dfrac k 2} = \floor {\dfrac {n^2} 4}$
Proof
By Permutation of Indices of Summation:
- $\ds \sum_{k \mathop = 1}^n \floor {\dfrac k 2} = \sum_{k \mathop = 1}^n \floor {\dfrac {n + 1 - k} 2}$
and so:
- $\ds \sum_{k \mathop = 1}^n \floor {\dfrac k 2} = \dfrac 1 2 \sum_{k \mathop = 1}^n \paren {\floor {\dfrac k 2} + \floor {\dfrac {n + 1 - k} 2} }$
First take the case where $n$ is even.
For $k$ odd:
- $\floor {\dfrac k 2} = \dfrac k 2 - \dfrac 1 2$
and:
- $\floor {\dfrac {n + 1 - k} 2} = \dfrac {n + 1 - k} 2$
Hence:
\(\ds \floor {\dfrac k 2} + \floor {\dfrac {n + 1 - k} 2}\) | \(=\) | \(\ds \dfrac k 2 - \dfrac 1 2 + \dfrac {n + 1 - k} 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {k - 1 + n + 1 - k} 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac n 2\) |
For $k$ even:
- $\floor {\dfrac k 2} = \dfrac k 2$
and:
- $\floor {\dfrac {n + 1 - k} 2} = \dfrac {n + 1 - k} 2 - \dfrac 1 2 = \dfrac {n - k} 2$
Hence:
\(\ds \floor {\dfrac k 2} + \floor {\dfrac {n + 1 - k} 2}\) | \(=\) | \(\ds \dfrac k 2 + \dfrac {n - k} 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {k + n - k} 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac n 2\) |
So:
\(\ds \sum_{k \mathop = 1}^n \floor {\dfrac k 2}\) | \(=\) | \(\ds \dfrac 1 2 \sum_{k \mathop = 1}^n \paren {\floor {\dfrac k 2} + \floor {\dfrac {n + 1 - k} 2} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac 1 2 \sum_{k \mathop = 1}^n \paren {\dfrac n 2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac 1 2 n \dfrac n 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {n^2} 4\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \floor {\dfrac {n^2} 4}\) | as $\dfrac {n^2} 4$ is an integer |
$\Box$
Next take the case where $n$ is odd.
For $k$ odd:
- $\floor {\dfrac k 2} = \dfrac k 2 - \dfrac 1 2$
and:
- $\floor {\dfrac {n + 1 - k} 2} = \dfrac {n + 1 - k} 2 - \dfrac 1 2$
Hence:
\(\ds \floor {\dfrac k 2} + \floor {\dfrac {n + 1 - k} 2}\) | \(=\) | \(\ds \dfrac k 2 - \dfrac 1 2 + \dfrac {n + 1 - k} 2 - \dfrac 1 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {k - 1 + n + 1 - k - 1} 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {n - 1} 2\) |
For $k$ even:
- $\floor {\dfrac k 2} = \dfrac k 2$
and:
- $\floor {\dfrac {n + 1 - k} 2} = \dfrac {n + 1 - k} 2$
Hence:
\(\ds \floor {\dfrac k 2} + \floor {\dfrac {n + 1 - k} 2}\) | \(=\) | \(\ds \dfrac k 2 + \dfrac {n - k + 1} 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {k + n - k + 1} 2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {n + 1} 2\) |
Let $n = 2 t + 1$.
Then:
\(\ds \sum_{k \mathop = 1}^n \floor {\dfrac k 2}\) | \(=\) | \(\ds \dfrac 1 2 \sum_{k \mathop = 1}^n \paren {\floor {\dfrac k 2} + \floor {\dfrac {n + 1 - k} 2} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac 1 2 \sum_{k \mathop = 1}^{2 t + 1} \paren {\floor {\dfrac k 2} + \floor {\dfrac {2 t + 2 - k} 2} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac t 2 \dfrac {\paren {2 t + 1} + 1} 2 + \dfrac {t + 1} 2 \dfrac {\paren {2 t + 1} - 1} 2\) | there are $t$ even terms and $t + 1$ odd terms | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {2 t^2 + 2 t} 4 + \dfrac {2 t^2 + 2 t} 4\) | multiplying out | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {4 t^2 + 4 t} 4 + \dfrac 1 4 - \dfrac 1 4\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {\paren {2 t + 1}^2} 4 - \dfrac 1 4\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {n^2} 4 - \dfrac 1 4\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \floor {\dfrac {n^2} 4}\) |
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $36$