next up previous index
Next: 4. The Complexification of Up: 3. Induction and Integers Previous: 3.4 Summation.   Index

3.5 Maximum Function

3.88   Definition ($\max (p,q)$.) Let $F$ be an ordered field, and let $p,q\in F$. We define

\begin{displaymath}\max(p,q)=\cases{p &if $p\geq q$\cr
q &if $p<q$.\cr}\end{displaymath}

Then

\begin{eqnarray*}
p&\leq&\max(p,q) \\
q&\leq&\max(p,q).
\end{eqnarray*}



3.89   Definition ( $\displaystyle {\max_{j\leq n\leq l} f(n)}$.) Let $F$ be an ordered field, let $j\in\mbox{{\bf Z}}$ and let $f\colon\mbox{{\bf Z}}_{\geq j}\to F$ be a function. Define $M\colon\mbox{{\bf Z}}_{\geq j}\to F$ by the rules

\begin{eqnarray*}
M(j)&=&f(j) \\
M(n+1)&=&\max\left(f(n+1),M(n)\right) \mbox{ for all } n\in\mbox{{\bf Z}}_{\geq j}.
\end{eqnarray*}



Hence, e.g., if $f(n)=(n-1)^2$,

\begin{eqnarray*}
M(0)&=&f(0)=1 \\
M(1)&=&\max\left(f(1),M(0)\right)=\max(0,1)=...
...)=\max(1,1)=1 \\
M(3)&=&\max\left(f(3),M(2)\right)=\max(4,1)=4.
\end{eqnarray*}



We write

\begin{displaymath}M(l)=\max_{j\leq m\leq l}f(m)\end{displaymath}

where $m$ is a dummy index, and we think of $M(l)$ as the largest of the numbers $\{f(j),f(j+1),\cdots ,f(l)\}$. By definition

\begin{displaymath}\max_{j\leq m\leq j}f(m)=f(j)\end{displaymath}

and

\begin{displaymath}\max_{j\leq m\leq l+1}=\max\left(f(j+1),\max_{j\leq m\leq l}f(m)\right).\end{displaymath}

3.90   Notation ( $\mbox{{\bf Z}}_{j\leq n\leq l}.$) Let $j,l\in\mbox{{\bf Z}}$ with $j\leq l$. Then

\begin{displaymath}\mbox{{\bf Z}}_{j\leq n\leq l}=\{n\in\mbox{{\bf Z}}\colon j\leq n\leq l\}.\end{displaymath}

3.91   Theorem. Let $F$ be an ordered field, let $j\in\mbox{{\bf Z}}$ and let $f\colon\mbox{{\bf Z}}_{\geq j}\to F$ be a function. Then for all $l\in\mbox{{\bf Z}}_{\geq j}$,
\begin{displaymath}
\mbox{ for all } p\in\mbox{{\bf Z}}_{j\leq m\leq l},
\;
f(p)\leq\max_{j\leq m\leq l}f(m).
\end{displaymath} (3.92)

Proof: Let $P$ be the proposition form on $\mbox{{\bf Z}}_{\geq j}$ such that $P(l)$ is the proposition (3.92). Then $P(j)$ says

\begin{displaymath}\mbox{ for all } p\in\mbox{{\bf Z}}_{j\leq m\leq j},\;
f(p)\leq\max_{j\leq m\leq j}f(m);\end{displaymath}

i.e.,

\begin{displaymath}\mbox{ for all } p\in\{j\},\;
f(p)\leq f(j).\end{displaymath}

Hence $P(j)$ is true.

Now for all $l\in\mbox{{\bf Z}}_{\geq j}$,

\begin{eqnarray*}
P(l) &\mbox{$\Longrightarrow$}& \mbox{ for all } p\in\mbox{{\b...
...{{\bf Z}}_{j\leq m\leq l},\; f(p)}
=\max_{j\leq m\leq
l+1}f(m).
\end{eqnarray*}



We also have

\begin{displaymath}f(l+1)\leq\max\left(f(l+1),\max_{j\leq m\leq l}f(m)\right)=\max_{j\leq m\leq
l+1}f(m),\end{displaymath}

so

\begin{eqnarray*}
P(l)&\mbox{$\Longrightarrow$}&\mbox{ for all } p\in\mbox{{\bf ...
...\leq\max_{j\leq m\leq l+1} \\
&\mbox{$\Longrightarrow$}&P(l+1).
\end{eqnarray*}



By induction, $P(l)$ is true for all $l\in\mbox{{\bf Z}}_{\geq j}$. $\mid\!\mid\!\mid$

3.93   Note. The notation $a^n$ for positive integer powers of $a$ was introduced by Descartes in 1637[15, vol 1,p 346]. Both Maple and Mathematica denote $a^n$ by a^n.


The notation $n!$ for the factorial of $n$ was introduced by Christian Kramp in 1808[15, vol 2, p 66].


The use of the Greek letter $\Sigma$ to denote sums was introduced by Euler in 1755[15, vol 2,p 61]. Euler writes

\begin{displaymath}\Sigma x^2 = {x^3 \over 3} -{x^2 \over 2} + {x\over 6}.\end{displaymath}

The use of limits on sums was introduced by Augustin Cauchy(1789-1857). Cauchy used the notation $\displaystyle{ \sum_m^n \!\!\!\! \mbox{\scriptsize$r$} \; fr}$ to denote what we would write as $\displaystyle{\sum_{r=m}^n f(r)}$[15, vol 2, p 61].

In Maple, the value of $\displaystyle {\sum_{i=1}^n f(i)}$ is denoted by sum(f(i),i=1..n)$\;$. In Mathematica it is denoted by Sum[f[i],{i,1,n}]$\;\;$.


next up previous index
Next: 4. The Complexification of Up: 3. Induction and Integers Previous: 3.4 Summation.   Index