False. On the unbounded subsequence of odd positive integers, $f(n)/g(n)=n$. For any proposed constants $C>0,N$, choose an odd $n>\max (C,N)$. Then $|f(n)|=n>C|g(n)|=C$, contradicting the eventual upper bound required by Big O notation. The small ratio on even integers cannot compensate for this failure on infinitely many odd integers.

True for every fixed $k\ge 0$. Extract $e^n$ from inside the logarithm:Choose an integer $m>k$. The nonnegative terms of the exponential series give $e^n\ge n^m/m!$ for $n>0$, whenceSince $0\le \log (1+u)\le u$ for $u\ge 0$, the displayed expression tends to zero and is therefore $O(1)$. The constant and cutoff may depend on the fixed $k$; no uniform assertion over unbounded $k$ is being made.

True. Rationalization gives, for $n\ge 1$,This lies between zero and $1/4$, so it is $O(1)$ in Big O notation. In fact it converges to $1/4$, rather than to zero. The rationalized form also avoids the catastrophic cancellation of subtracting two nearby large quantities.

False. Put $r_n=3^n/n^3$ for $n\ge 1$. For $n\ge 4$,Thus $r_n\ge r_4(192/125{)}^{n-4}\to \infty$. No fixed constant can bound $3^n/n^3$ eventually, so $3^n\ne O(n^3)$. This is an explicit comparison of exponential growth with polynomial growth.

True. For every integer $n\ge 1$, $n^2\le n^3$ and $1\le n^3$. ThereforeThe constants $C=1097$ and $N=1$ satisfy the definition of Big O notation. Whether the chosen convention for natural numbers includes zero is immaterial to this eventual assertion.

The term $x+z$ is free for substitution for $z$. The only free occurrence of the target $z$ is in the outside disjunct $y<z$, beyond both quantifier scopes. The occurrences under $\forall z$ are bound variables and are not replaced. Therefore no renaming is required, andThe new $x$ and $z$ in the last disjunct are free. First-order substitution replaces the original free occurrences once; it does not recursively substitute into the inserted term.

The term $x+z$ is not free for substitution for $y$. The occurrence of $y$ in $x<y$ is under $\exists x$, which would capture the inserted $x$. The other occurrence, in the outside disjunct $y<z$, has no enclosing quantifier. The inner $\forall z$ does not bind the occurrence of $y$ in its antecedent, so it creates no additional capture at that substitution site.

Rename the bound $x$ to a fresh $u$, then carry out capture-avoiding first-order substitution. The result isThe inserted $z$ in $u<x+z$ remains free because it lies outside the scope of $\forall z$. One may additionally rename that bound $z$ for readability, but it is not necessary for correctness.

Define $f:W_1\cap W_2\to U$ by $f(u)=(u,-u)$. It is well-defined by the definition of $U$, andThus $f$ is a linear map. If $f(u)=f(v)$, comparing first components gives $u=v$, proving injectivity. Every element of $U$ has the form $(u,-u)=f(u)$, proving surjectivity. Hence $f$ is a linear isomorphism, with inverse $(u,-u)\mapsto u$, and $\dim U=\dim (W_1\cap W_2)$.

The intersection of vector subspaces $W_1\cap W_2$ contains zero, so $(0,0)\in U$. If $(u,-u),(v,-v)\in U$ and $a,b$ are scalars, thenbecause $au+bv\in W_1\cap W_2$ by the vector subspace conditions. These pairs belong to $W_1\times W_2$, since both $u$ and $-u$ belong to the required factors. Thus $U$ is a vector subspace of $W_1\times W_2$.

Evaluate the recurrence relation successively, retaining only the preceding two values. Each of the $n-1$ updates uses three multiplications and one subtraction. Hence $4(n-1)=O(n)$ arithmetic operations and $O(1)$ auxiliary storage suffice, excluding the stored input. Naively branching into two recursive calls would repeat work; the sequential computation is essential. This is an arithmetic-operation bound, not a bit-complexity bound for arbitrarily large exact integers.

Let $f_j$ be the determinant of the leading $j\times j$ principal submatrix. Expansion along the last row gives an $a_j{f}_{j-1}$ term and a $c_{j-1}$ term with negative cofactor sign. In the latter minor, the final column has only $b_{j-1}$ nonzero, and deleting that row and column leaves the leading $(j-2)\times (j-2)$ principal submatrix. Thus the tridiagonal determinant recurrence isHere $f_0=1$ is the empty determinant convention, needed to include $f_2=a_1{a}_2-b_1{c}_1$. The derivation uses cofactor expansion, so the recurrence relation remains valid when coefficients or intermediate determinants vanish; it never divides by a pivot element.

They are similar matrices, so their eigenvalues, with algebraic multiplicities, are identical. Explicitly,Moreover their eigenvectors correspond by $Av=\lambda v⟺(D^{-1}AD)(D^{-1}v)=\lambda D^{-1}v$. Since the transformed matrix is a real symmetric matrix, the spectral theorem for real symmetric matrices also shows that $A$ has real eigenvalues and is a diagonalizable matrix.

For the analogous positive off-diagonal entries in size $n$, takeThe same entrywise computation gives $(D^{-1}AD{)}_{ii}=a_i$ and $(D^{-1}AD{)}_{i,i+1}=(D^{-1}AD{)}_{i+1,i}=\sqrt{b_i{c}_i}$, with every other entry zero. Thus the result is a symmetric matrix with a tridiagonal pattern. Positivity of the diagonal entries $a_i$ is not needed for this positive diagonal symmetrization of a tridiagonal matrix; positivity of $b_i,c_i$ ensures the displayed positive, invertible $D$. In particular, the assertion is not an arbitrary-real-coefficient symmetrization claim when the off-diagonal signs differ.

For $D=\mathrm{diag}(d_1,d_2,d_3)$, the upper entry of $D^{-1}AD$ in positions $i,i+1$ is $b_i{d}_{i+1}/d_i$, and the corresponding lower entry is $c_i{d}_i/d_{i+1}$. They are equal when $(d_{i+1}/d_i{)}^2=c_i/b_i$. All coefficients used here are positive, so chooseDirect matrix multiplication gives the symmetric matrixIts pattern remains tridiagonal. This is positive diagonal symmetrization of a tridiagonal matrix.

Write $B=QD{Q}^{-1}$ with $D$ a diagonal matrix. Then $0=B^k=Q{D}^k{Q}^{-1}$, so each diagonal entry ${\lambda }_i$ satisfies ${\lambda }_i^k=0$ and therefore ${\lambda }_i=0$. Hence $D=0$ and $B=0$. Conversely the zero matrix is diagonalizable and nilpotent. This proves the existing result that a diagonalizable nilpotent matrix is zero; nilpotence alone does not imply a zero matrix, because nonzero nilpotent Jordan blocks exist.

If $B^k=0$ with $k\ge 1$, put $S=I+B+\cdots +B^{k-1}$. The matrix geometric series telescopes on both sides:Thus $I-B$ is nonsingular, andThis is a finite polynomial identity for a nilpotent matrix; no convergence argument or bound $\Vert B\Vert <1$ is required.

The all-ones matrix is diagonalizable for every $n\ge 1$. The vector $u$ together with the $n-1$ vectors from part (ii) is an eigenbasis. Independence follows because a multiple of $u$ has coordinate sum $n$ times that multiple, whereas every other basis vector has coordinate sum zero. In this basis the diagonal matrix is $\mathrm{diag}(n,0,\dots ,0)$. At $n=1$ the one-vector basis suffices. Alternatively, the spectral theorem for real symmetric matrices applies. If dimension zero is allowed by the convention for $\mathbb{N}$, the empty $0\times 0$ matrix has no eigenvalues, an empty basis and a vacuous diagonalization.

The decomposition into $\mathrm{span}\{u\}$ and the zero-sum vector subspace gives characteristic polynomial $t^{n-1}(t-n)$. For $n\ge 2$, $n$ has algebraic multiplicity and geometric multiplicity one; zero has both multiplicities $n-1$. At $n=1$, only the eigenvalue 1 occurs, with both multiplicities one. Referring to a multiplicity zero for the absent root zero is merely a bookkeeping convention, not an assertion that it is an eigenvalue.

A basis of $E_n$ is $\{u\}$. For $n\ge 2$,The displayed vectors are linearly independent by their first $n-1$ coordinates, and every vector with zero coordinate sum has exactly that expansion. At $n=1$ this list is empty and the kernel is $\{0\}$; it is not an additional eigenspace associated with a present eigenvalue. This is the spectrum of an all-ones matrix.

Assume $n\ge 1$. With $u=(1,\dots ,1{)}^T$, the all-ones matrix satisfies $Av=({\sum }_j{v}_j)u$. Hence $n$ is an eigenvalue, and for $n\ge 2$ the other eigenvalue is $0$. At $n=1$ the matrix is $[1]$, so 1 is its only eigenvalue; zero is not an eigenvalue with a nonzero eigenvector in that case.