Question 5 of 12

Question 5

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Two propositional-logic claims to prove, the standard definition target for Big-O, and a linear recurrence with an explicit closed form (verified below against the stated initial conditions).

Find. (a) a logical-equivalence proof and a tautology proof; (b-a) the formal Big-O definition; (b-b) the smallest base $x$ with $a_n=O(x^n)$.

Approach. Use the standard $\to\equiv\neg\vee$ rewriting and De Morgan/associativity for the equivalence; use the absorption law for the tautology; and analyze the closed form's dominant exponential term for the growth-rate question.

1. 5a-i) $p\to(q\to r)\equiv(p\land q)\to r$. Rewrite implications as disjunctions and regroup: $$p\to(q\to r)\equiv \neg p\lor(q\to r)\equiv \neg p\lor(\neg q\lor r)\equiv(\neg p\lor\neg q)\lor r \equiv \neg(p\land q)\lor r \equiv (p\land q)\to r$$ using associativity of $\lor$ and De Morgan's law $\neg p\lor\neg q\equiv\neg(p\land q)$ in the last two steps. $\boxed{p\to(q\to r)\equiv(p\land q)\to r}$
2. 5a-ii) $((a\land p)\lor p)\to p$ is a tautology. By the absorption law, $(a\land p)\lor p\equiv p$ (a conjunction "or'd" with one of its own conjuncts collapses to that conjunct). Substituting, the whole formula becomes $p\to p$, which is true under every truth assignment. $\boxed{((a\land p)\lor p)\to p \text{ is a tautology (via absorption, reduces to } p\to p\text{)}}$
3. 5b-a) Big-O definition. $a_n=O(f(n))$ means there exist constants $C>0$ and $N\in\mathbb{N}$ such that $|a_n|\leq C\,|f(n)|$ for all $n\geq N$ — i.e. $a_n$ is eventually bounded above (up to a constant factor) by $f(n)$.
4. 5b-b) Smallest base for $a_n=O(x^n)$. Let $\varphi=\dfrac{1+\sqrt5}{2}\approx1.618$ and $\psi=\dfrac{1-\sqrt5}{2}\approx-0.618$ (so $|\psi|\lt1$). Then $a_n=\varphi^{n+1}+\psi^{n+1}=\varphi\cdot\varphi^{n}+\psi\cdot\psi^{n}$. Since $|\psi|\lt1$, $\psi^n\to0$, so $a_n/\varphi^n\to\varphi\neq0$ — the sequence grows at exactly the rate $\varphi^n$ (a nonzero-limit ratio), which means $a_n=O(\varphi^n)$ but $a_n\neq O(x^n)$ for any $x\lt\varphi$ (the ratio $a_n/x^n\to\infty$ in that case, since $(\varphi/x)^n\to\infty$). $$x_{\min}=\varphi=\frac{1+\sqrt5}{2}\approx1.618$$ $\boxed{x_{\min}=\dfrac{1+\sqrt5}{2}}$