Set $h=(b-a)/n$ and $x_i=a+ih$. Summing the areas of the $n$ endpoint trapezia gives the composite trapezoidal ruleEvery interior value is shared by two adjacent strips; the two endpoint values occur only once with half weight. Evenness of $n$ is not needed for this rule.

Apply integration by parts with $u=x$ and $dv=\sin (\mu x)dx$. Part (i) gives $v=-\cos (\mu x)/\mu$, so

The chain rule gives $\frac{d}{dx}\cos (\mu x)=-\mu \sin (\mu x)$. Dividing by the nonzero constant $-\mu$ gives the antiderivative

We prove the stronger explicit bound $n!\le n^n/2^{n-1}$ by mathematical induction. The case $n=1$ is equality. The binomial theorem gives $(1+1/n{)}^n\ge 1+n/n=2$, so $(n+1{)}^n\ge 2n^n$. Consequently the induction hypothesis yieldsTherefore $n!=O(n^n/2^n)$, with constant $2$ and threshold $1$.

The second bound is asymptotically tighter. Using $n\le 2^n$,Thus its bounding function is negligible relative to the first in little o notation; this compares the bounds without needing Stirling's formula.

Prove the explicit bound $n!\le 2^{n^2}$ by mathematical induction. At $n=1$, $1\le 2$. For the step, note that $n+1\le 2^n$ for $n\ge 1$: this auxiliary inequality has base $2=2$ and follows at the next index from $n+2\le 2(n+1)$. Hence, using the induction hypothesis,Thus $n!=O((2^n{)}^n)$, with constant $1$ and threshold $1$ in big O notation.

For each fixed positive integer $k$, part (i) gives $(f(n)+g(n){)}^k\le (2h(n){)}^k=2^{k}h(n{)}^k$. This meets big O notation with constant $2^k$ and threshold $1$. True: $(f+g{)}^k=O(h^k)$ for fixed $k$. The constant may depend on $k$; no claim uniform in a varying $k$ is required.

Take $f(n)=g(n)=n^2$, so $h(n)=n^2$ but $(f\circ g)(n)=n^4$. The ratio $(f\circ g)(n)/h(n)=n^2$ is unbounded, precluding any eventual constant upper bound in big O notation. False: in general $f\circ g\ne O(h)$. This is a counterexample involving function composition, not pointwise addition.

Positivity gives $\max \{f(n),g(n)\}\le f(n)+g(n)$. Thus $h(n)\le f(n)+g(n)$ for every positive $n$, meeting big O notation with constant $1$ and threshold $1$. True: $h=O(f+g)$.

Since $h(n)=\max \{f(n),g(n)\}$, both $f(n)\le h(n)$ and $g(n)\le h(n)$. Therefore $f(n)+g(n)\le 2h(n)$ for every positive $n$. The definition of big O notation is satisfied with constant $2$ and threshold $1$. True: $f+g=O(h)$.

Suppose $m$ is the greatest lower bound of the set $X$ of all upper bounds of $S$. Every $s\in S$ satisfies $s⪯x$ for every $x\in X$, so each such $s$ is a lower bound of $X$. Since $m$ is the greatest of those lower bounds, $s⪯m$ for every $s\in S$. Thus $m$ itself is an upper bound of $S$, meaning $m\in X$.

Also $m$, being a lower bound of $X$, satisfies $m⪯x$ for every $x\in X$. It is therefore an upper bound of $S$ below every other upper bound, which proves $m=\mathrm{lub}(S)$. The argument also covers empty $S$ or $X$ whenever the assumed greatest lower bound exists.

In the partially ordered set $(A,⪯)$, the assertion $m=\mathrm{lub}(S)$ means bothThe first condition makes $m$ an upper bound; the second makes it the least upper bound. Both conditions are necessary, and antisymmetry makes such an element unique.

The relation powers are $R^2=\{(a,c),(b,d)\}$, $R^3=\{(a,d)\}$, and $R^i=\varnothing$ for $i\ge 4$. For $k=1$, $(a,b),(b,c)\in T$ but $(a,c)\notin T$, so transitivity fails. For $k=2$, $(a,c),(c,d)\in T$ but $(a,d)\notin T$, so it still fails.

For $k=3$, $T$ consists of every pair in which the first endpoint precedes the second in $a,b,c,d$. Composing any two such pairs again gives such a pair, so $T$ is transitive. Thus the smallest $k$ is $3$; this $T$ is the transitive closure of a relation $R$.

A pair belongs to $R\circ R$ exactly when two successive $R$ steps connect its endpoints. The chain $a\to b\to c\to d$ has two such length-two paths, $a\to b\to c$ and $b\to c\to d$. HenceThis applies composition of relations directly; no other middle element gives a pair.

Using the wiki convention that paths follow the written order of the binary relations, composition of relations isSome treatments reverse the naming convention; stating it explicitly avoids ambiguity. The powers of the single relation $R$ below are the same under either convention.

Choose the image of a function as a $j$-element subset of $B$, then choose a surjection onto that selected image as in (iii). ThereforeThe answer is zero when $j>n$. If $j=0$, it is one for $m=0$ and zero for $m>0$, as the Stirling numbers of the second kind conventions require.

For a surjection, the nonempty fibres $f^{-1}(b)$ form a partition of a set $A$ into exactly $n$ blocks. Choose these unlabelled blocks in $S(m,n)$ ways, then assign the $n$ distinct elements of $B$ to them in $n!$ ways. ConsequentlyIt is zero when $m<n$. With $S(0,0)=1$ and $S(m,0)=0$ for $m>0$, the same formula also handles an empty set codomain.

A bijection between finite sets requires equal cardinality. When $m=n$, list the elements of $A$ and choose their distinct images in $n,n-1,\dots ,1$ ways. ThusThe factorial convention $0!=1$ includes the unique bijection from the empty set to itself.

Each of the $m$ elements of $A$ independently receives one of $n$ images in $B$. The multiplication principle therefore gives $n^m$ functions. In particular an empty set domain has exactly one function to any $B$, so here $0^0$ is interpreted as $1$; a nonempty domain has no function to an empty set codomain.

Starting from $n$ singleton blocks, a partition of a set into $n-1$ nonempty blocks has exactly one block of size two and all other blocks of size one: the sum of the block sizes exceeds the number of blocks by exactly one. Choosing that pair determines the partition uniquely. HenceThis fixed value of $k$ works for every $n\ge 2$. It is forced already by $n=2$: $S(2,1)=1$, whereas for positive $k$ the only $\left(\genfrac{}{}{0ex}{}{2}{k}\right)$ equal to one is $\left(\genfrac{}{}{0ex}{}{2}{2}\right)$.

Fix one distinguished element $a$ of the $n$-element set. Every partition of a set into $l$ blocks belongs to exactly one of two cases. If $\{a\}$ is a block, removing it leaves an $(l-1)$-block partition of a set of the other $n-1$ elements, giving $S(n-1,l-1)$ possibilities. Otherwise remove $a$ from its block; that block remains nonempty, so the result has $l$ blocks. Conversely choose any of the $S(n-1,l)$ such partitions and insert $a$ in any one of its $l$ blocks. This gives $lS(n-1,l)$ possibilities.

These cases are disjoint and exhaustive, proving the Stirling numbers of the second kind recurrenceUse $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,l)=0$ for $l>n$; these conventions include the boundary cases $n=1$ and $l=1$.