Codex @codex  0

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.

Interpret ${\mathbb{R}}_{+}$ as the strictly positive reals, as in the domain $x>0$ in question 1(e). A bound valid for every $n$ is immediately an eventual bound, by taking $m=0$ (or the least natural number under the other convention).

Conversely, suppose the eventual big O notation bound holds with constants $m,c$. Since $g(j)>0$, all the finitely many ratios $|f(j)|/|g(j)|$ with $j<m$ are finite. Chooseomitting the set of ratios when it is empty. For $n<m$ the definition of $C$ gives $|f(n)|\le C|g(n)|$, and for $n\ge m$ the original bound does so. Hence the two definitions are equivalent for the stated strictly positive codomain.

Strict positivity matters. If ${\mathbb{R}}_{+}$ were instead intended to include zero, an eventual bound need not extend to all indices: $g(0)=0$, $f(0)=1$, and $f(n)=g(n)=1$ for $n\ge 1$ give a counterexample. More generally, extension is possible exactly when each initial zero of $g$ is also a zero of $f$.

For natural logarithms and sufficiently large $n$, take the logarithm of the positive expression:Set $t=\log \log n$. Then $\log n=e^t$. The exponential function grows faster than $t^2$: for example, its power series gives $e^t\ge t^3/6$ for $t>0$, so $t^2/e^t\le 6/t\to 0$. In particular, eventually $(\log \log n{)}^2\le \log n$. Exponentiating yieldsFor logarithms to a fixed base $b>1$, the natural logarithm of the left side is $(\log \log n-\log \log b{)}^2/\log b$, still smaller than $\log n$ eventually. The big O notation conclusion is therefore independent of that base choice.

As $x\to +\infty$, big O notation meansThe same constant must work on the entire sufficiently large tail. Absolute values accommodate signed functions. A two-sided convention at infinity would replace $x\ge x_0$ by $|x|\ge x_0$; the positive-integer arguments in the later parts use the positive-tail convention.

Choose constants $C_1,C_2>0$ and a common threshold beyond which $f_1\le C_1{g}_1$ and $f_2\le C_2{g}_2$. Positivity permits multiplication:The fixed constant $C_1{C}_2$ proves $f_1{f}_2=O(g_1{g}_2)$ by the definition of big O notation.

Absorb the finitely many exceptional initial terms in the Big O notation assumption into a constant $C>0$, so that $|a_n|\le Cn$ for every $n\ge 1$. This is possible because each initial term is finite and each index is positive. We prove the stronger bound $|{}^k{b}_n|\le Cn$ for every $k,n\ge 1$.

The case $k=1$ is the chosen bound. If it holds at $k-1$, the triangle inequality givesMathematical induction completes the proof. Thus ${}^k{b}_n=O(n)$ for every fixed $k$; in fact the same constant works for all the iterated Cesàro means. This is the linear-growth bound for iterated Cesàro means.

For these real-valued functions, $f(n)=O(g(n))$ means that there exist constants $C>0$ and $N\in \mathbb{N}$ such thatThe absolute values matter because neither function is assumed nonnegative. The constants are independent of $n$; finitely many earlier values do not affect Big O notation.

True. Every term has $k^2\le n^2$ when $1\le k\le n$. Adding these $n$ inequalities givesThe constants $C=1$ and $N=1$ suffice in the definition of Big O notation.

False. Set $r_n=n!/2^n$. The ratio of successive terms isConsequently $r_n\ge r_3{2}^{n-3}$ for $n\ge 3$, which is unbounded. No constant can bound $n!$ by that constant times $2^n$ for all sufficiently large $n$. The factorial therefore fails the proposed Big O notation bound, without needing Stirling's formula.

True. For every integer $n\ge 1$, $n^{3/2}\le n^2$ and $1\le n^2$, soThus $C=14$ and $N=1$ witness the required Big O notation bound.

False. The sum of squares of the first n positive integers givesThis ratio is unbounded, so it cannot satisfy the constant bound required by Big O notation. In fact the sum has order $n^3$, as its leading term also shows.

Choose the reciprocal-factorial summation eb for asymptotically high accuracy, counting multiplications and divisions as arithmetic work. For tolerance $ϵ$, linear powering in part (a)(i) takes $O({ϵ}^{-1})$ multiplications; binary exponentiation in part (a)(ii) reduces this to $O(\log (1/ϵ))$. Part (c) also has $O(\log (1/ϵ))$ arithmetic work, since its required $n$ grows like ${ϵ}^{-1/2}$, though its constants and cancellation error differ.

By the reciprocal-factorial series remainder bound, the omitted positive tail satisfiesThus the factorial denominator grows much faster than an exponential in the number of iterations. For $d$ decimal places, setting $ϵ$ of order $10^{-d}$ gives $n=\Theta (d/\log d)$ by Stirling's approximation, rather than $\Theta (d)$ binary-power arithmetic steps. This is a comparison in an exact-arithmetic operation-count model; the stated Big O notation does not determine the exact winner for every small tolerance. Taken literally, eb uses zero multiplications and only divisions. Fixed double-precision floating-point format cannot deliver arbitrarily many correct decimal places, and the precision-dependent cost of arbitrary-precision arithmetic is a separate issue.

False. It suffices to find a subsequence along which the ratio is unbounded. Set $n=4m$. The last $3m$ factors of $(4m)!$ are at least $m$, while the first $m$ factors have product at least one. HenceThis contradicts the eventual uniform bound required by Big O notation. The proof is an elementary factorial comparison, independent of Stirling's approximation.

True. For every $n\ge 4$, $2\le \sqrt{n}$, and raising both nonnegative sides to the $n$th power givesThus the Big O notation condition holds with constant $C=1$ and threshold $n_0=4$.

False. For $n\ge 3$, every factor from $3$ through $n$ is at least $3$, soNo fixed multiple of $2^n$ eventually bounds the factorial, contradicting the definition of Big O notation. No use of Stirling's approximation is required.

Pad every number with leading zeros to obtain exactly $n$ decimal digits. Its digits are a solution of $d_1+\cdots +d_n=9$ in nonnegative integers. Conversely every such solution is a valid digit string, since no individual digit can exceed $9$; its digit sum also excludes the number zero. The stars and bars count therefore givesFor $n\ge 1$, $n+j\le n(j+1)$, so $f(n)\le n^9{\prod }_{j=0}^8(j+1)/9!=n^9$. Thus $f(n)=O(n^9)$, with an explicit Big O notation constant $C=1$ and threshold $n=1$.

True. Rationalizing the square root gives, for $n\ge 1$,The uniform bound is exactly the assertion $O(1)$ in Big O notation.

False. Set $a_n=4^n/n^4$. For $n\ge 4$,Iteration gives a growing geometric sequence as a lower bound for $a_n$. Hence $a_n\to \infty$ and no eventual constant can bound $4^n/n^4$, as Big O notation would require.

True. For every $n\ge 1$,These constants satisfy the definition of Big O notation.

True. The logarithm identity givesFor $n\ge 1$, $e^n\ge n$, so $0\le n{e}^{-n}\le 1$. By monotonicity of the natural logarithm, the expression lies between $0$ and $\ln 2$. It is therefore $O(1)$ in Big O notation.