Summation over k of Ceiling of k over 2

From ProofWiki
Jump to navigation Jump to search

Theorem

$\ds \sum_{k \mathop = 1}^n \ceiling {\dfrac k 2} = \ceiling {\dfrac {n \paren {n + 2} } 4}$


Proof

By Permutation of Indices of Summation:

$\ds \sum_{k \mathop = 1}^n \ceiling {\dfrac k 2} = \sum_{k \mathop = 1}^n \ceiling {\dfrac {n + 1 - k} 2}$

and so:

$\ds \sum_{k \mathop = 1}^n \ceiling {\dfrac k 2} = \dfrac 1 2 \sum_{k \mathop = 1}^n \paren {\ceiling {\dfrac k 2} + \ceiling {\dfrac {n + 1 - k} 2} }$


First take the case where $n$ is even.


For $k$ odd:

\(\ds \ceiling {\dfrac k 2}\) \(=\) \(\ds \dfrac k 2 + \dfrac 1 2\) Definition of Ceiling Function

and:

\(\ds \ceiling {\dfrac {n + 1 - k} 2}\) \(=\) \(\ds \dfrac {n + 1 - k} 2\) Definition of Ceiling Function

Hence:

\(\ds \ceiling {\dfrac k 2} + \ceiling {\dfrac {n + 1 - k} 2}\) \(=\) \(\ds \dfrac k 2 + \dfrac 1 2 + \dfrac {n + 1 - k} 2\) from above
\(\ds \) \(=\) \(\ds \dfrac {k + 1 + n + 1 - k} 2\)
\(\ds \) \(=\) \(\ds \dfrac {n + 2} 2\)


For $k$ even:

\(\ds \ceiling {\dfrac k 2}\) \(=\) \(\ds \dfrac k 2\) Definition of Ceiling Function

and:

\(\ds \ceiling {\dfrac {n + 1 - k} 2}\) \(=\) \(\ds \dfrac {n + 1 - k} 2 + \dfrac 1 2\) Definition of Ceiling Function
\(\ds \) \(=\) \(\ds \dfrac {n - k + 2} 2\)

Hence:

\(\ds \ceiling {\dfrac k 2} + \ceiling {\dfrac {n + 1 - k} 2}\) \(=\) \(\ds \dfrac k 2 + \dfrac {n - k + 2} 2\) from above
\(\ds \) \(=\) \(\ds \dfrac {k + n - k + 2} 2\)
\(\ds \) \(=\) \(\ds \dfrac {n + 2} 2\)


So:

\(\ds \sum_{k \mathop = 1}^n \ceiling {\dfrac k 2}\) \(=\) \(\ds \dfrac 1 2 \sum_{k \mathop = 1}^n \paren {\ceiling {\dfrac k 2} + \ceiling {\dfrac {n + 1 - k} 2} }\)
\(\ds \) \(=\) \(\ds \dfrac 1 2 \sum_{k \mathop = 1}^n \paren {\dfrac {n + 2} 2}\)
\(\ds \) \(=\) \(\ds \dfrac 1 2 n \paren {\dfrac {n + 2} 2}\)
\(\ds \) \(=\) \(\ds \dfrac {n \paren {n + 2} } 4\) Definition of Ceiling Function
\(\ds \) \(=\) \(\ds \ceiling {\dfrac {n \paren {n + 2} } 4}\) as $\dfrac {n \paren {n + 2} } 4$ is an integer

$\Box$


Next take the case where $n$ is odd.


For $k$ odd:

\(\ds \ceiling {\dfrac k 2}\) \(=\) \(\ds \dfrac k 2 + \dfrac 1 2\) Definition of Ceiling Function

and:

\(\ds \ceiling {\dfrac {n + 1 - k} 2}\) \(=\) \(\ds \dfrac {n + 1 - k} 2 + \dfrac 1 2\) Definition of Ceiling Function

Hence:

\(\ds \ceiling {\dfrac k 2} + \ceiling {\dfrac {n + 1 - k} 2}\) \(=\) \(\ds \dfrac k 2 + \dfrac 1 2 + \dfrac {n + 1 - k} 2 + \dfrac 1 2\) from above
\(\ds \) \(=\) \(\ds \dfrac {k + 1 + n + 1 - k + 1} 2\)
\(\ds \) \(=\) \(\ds \dfrac {n + 3} 2\)


For $k$ even:

$\ceiling {\dfrac k 2} = \dfrac k 2$

and:

$\ceiling {\dfrac {n + 1 - k} 2} = \dfrac {n + 1 - k} 2$

Hence:

\(\ds \ceiling {\dfrac k 2} + \ceiling {\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 \ceiling {\dfrac k 2}\) \(=\) \(\ds \dfrac 1 2 \sum_{k \mathop = 1}^n \paren {\ceiling {\dfrac k 2} + \ceiling {\dfrac {n + 1 - k} 2} }\)
\(\ds \) \(=\) \(\ds \dfrac 1 2 \sum_{k \mathop = 1}^{2 t + 1} \paren {\ceiling {\dfrac k 2} + \ceiling {\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} + 3} 2\) there are $t$ even terms and $t + 1$ odd terms
\(\ds \) \(=\) \(\ds \dfrac {2 t^2 + 2 t} 4 + \dfrac {2 t^2 + 6 t + 4} 4\) multiplying out
\(\ds \) \(=\) \(\ds \dfrac {4 t^2 + 8 t + 3} 4 + \dfrac 1 4\)
\(\ds \) \(=\) \(\ds \dfrac {\paren {2 t + 1} \paren {2 t + 3} } 4 + \dfrac 1 4\)
\(\ds \) \(=\) \(\ds \dfrac {n \paren {n + 2} } 4 + \dfrac 1 4\)
\(\ds \) \(=\) \(\ds \ceiling {\dfrac {n \paren {n + 2} } 4}\) Definition of Ceiling Function

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Summation_over_k_of_Ceiling_of_k_over_2&oldid=630366"