Instructions
- Proofs must be rigorous and complete.
- Write legibly. Illegible answers will not be graded.
- No devices, books, or notes allowed.
- Use only the space allocated.
Q1
Proof by Strong Induction
5 pts
Let \( f_n \) denote the \( n \)-th Fibonacci number defined by \( f_0 = 0 \), \( f_1 = 1 \), and \( f_n =
f_{n-1} + f_{n-2} \) for \( n \geq 2 \).
Prove by strong induction that for all \( n \geq 1 \): \[ f_n < \left(\frac{7}{4}\right)^n \]
Prove by strong induction that for all \( n \geq 1 \): \[ f_n < \left(\frac{7}{4}\right)^n \]
Solution:
We prove \( f_n < \left(\frac{7}{4}\right)^n \) for all \( n \geq 1 \) by strong induction.
Base Cases: \( f_1 = 1 < \frac{7}{4} \) and \( f_2=1 < \frac{49}{16} \). Both hold.
Inductive Step: Assume \( f_k < \left(\frac{7}{4}\right)^k \) for all \( 1 \leq k \leq n \). Then: \[ \begin{aligned} f_{n+1} &=f_n + f_{n-1} < \left(\frac{7}{4}\right)^n + \left(\frac{7}{4}\right)^{n-1}\\ &=\left(\frac{7}{4}\right)^{n-1}\left(\frac{7}{4} + 1\right)=\left(\frac{7}{4}\right)^{n-1} \cdot \frac{11}{4} \end{aligned} \] Since \( \frac{11}{4}=\frac{44}{16} < \frac{49}{16}=\left(\frac{7}{4}\right)^2 \), we have: \[ f_{n+1} < \left(\frac{7}{4}\right)^{n-1} \cdot \left(\frac{7}{4}\right)^2=\left(\frac{7}{4}\right)^{n+1} \]
Base Cases: \( f_1 = 1 < \frac{7}{4} \) and \( f_2=1 < \frac{49}{16} \). Both hold.
Inductive Step: Assume \( f_k < \left(\frac{7}{4}\right)^k \) for all \( 1 \leq k \leq n \). Then: \[ \begin{aligned} f_{n+1} &=f_n + f_{n-1} < \left(\frac{7}{4}\right)^n + \left(\frac{7}{4}\right)^{n-1}\\ &=\left(\frac{7}{4}\right)^{n-1}\left(\frac{7}{4} + 1\right)=\left(\frac{7}{4}\right)^{n-1} \cdot \frac{11}{4} \end{aligned} \] Since \( \frac{11}{4}=\frac{44}{16} < \frac{49}{16}=\left(\frac{7}{4}\right)^2 \), we have: \[ f_{n+1} < \left(\frac{7}{4}\right)^{n-1} \cdot \left(\frac{7}{4}\right)^2=\left(\frac{7}{4}\right)^{n+1} \]
Q2
Incomplete Proof - Fill the Gaps
5 pts
Below is a proof that \( \sqrt{3} \) is irrational with several steps missing. Fill in the blanks with
the correct mathematical statements or justifications.
Proof: Assume for contradiction that \( \sqrt{3} \) is rational. Then there exist coprime integers \( a, b \) with \( b \neq 0 \) such that \( \sqrt{3} = \frac{a}{b} \).
Squaring both sides: \(\_\_\_\_\_\) (Step A)
Therefore, 3 divides \( a^2 \). Since 3 is prime, this implies \(\_\_\_\_\_\) (Step B)
We can write \( a = 3k \) for some integer \( k \). Substituting into our earlier equation: \[ \_\_\_\_\_\_\_\_\_\_ \textbf{(Step C)} \] Simplifying: \(\_\_\_\_\_\) (Step D)
This means 3 divides \( b^2 \), and by the same reasoning, \(\_\_\_\_\_\) (Step E)
But this contradicts our assumption that \( \gcd(a,b) = 1 \). Therefore, \( \sqrt{3} \) is irrational.
Proof: Assume for contradiction that \( \sqrt{3} \) is rational. Then there exist coprime integers \( a, b \) with \( b \neq 0 \) such that \( \sqrt{3} = \frac{a}{b} \).
Squaring both sides: \(\_\_\_\_\_\) (Step A)
Therefore, 3 divides \( a^2 \). Since 3 is prime, this implies \(\_\_\_\_\_\) (Step B)
We can write \( a = 3k \) for some integer \( k \). Substituting into our earlier equation: \[ \_\_\_\_\_\_\_\_\_\_ \textbf{(Step C)} \] Simplifying: \(\_\_\_\_\_\) (Step D)
This means 3 divides \( b^2 \), and by the same reasoning, \(\_\_\_\_\_\) (Step E)
But this contradicts our assumption that \( \gcd(a,b) = 1 \). Therefore, \( \sqrt{3} \) is irrational.
Solution:
Step A: \( 3 = \frac{a^2}{b^2} \), therefore \( 3b^2 = a^2 \)
Step B: 3 divides \( a \)
Step C: \( 3b^2 = (3k)^2 = 9k^2 \)
Step D: \( b^2 = 3k^2 \)
Step E: 3 divides \( b \)
Step B: 3 divides \( a \)
Step C: \( 3b^2 = (3k)^2 = 9k^2 \)
Step D: \( b^2 = 3k^2 \)
Step E: 3 divides \( b \)
Q3
Logical Equivalence with Quantifiers
5 pts
Prove or disprove: For predicates \( P(x) \) and \( Q(x) \) over domain \( D \), the following are
logically equivalent:
\[ \neg(\forall x\, P(x) \to \exists x\, Q(x)) \equiv \forall x\, P(x) \land \forall x\, \neg Q(x) \]
If they are equivalent, provide a formal derivation using logical equivalence laws. If not, provide a
counterexample with a specific domain and predicates.
Solution:
The statements are logically equivalent.
Derivation: \[ \begin{aligned} \neg(\forall x\, P(x) \to \exists x\, Q(x)) &\equiv \neg(\neg\forall x\, P(x) \lor \exists x\, Q(x))\\ &\equiv \forall x\, P(x) \land \neg\exists x\, Q(x)\\ &\equiv \forall x\, P(x) \land \forall x\, \neg Q(x) \end{aligned} \] using the equivalences: \( A \to B \equiv \neg A \lor B \), De Morgan's law, and \( \neg\exists x\, Q(x) \equiv \forall x\, \neg Q(x) \).
Derivation: \[ \begin{aligned} \neg(\forall x\, P(x) \to \exists x\, Q(x)) &\equiv \neg(\neg\forall x\, P(x) \lor \exists x\, Q(x))\\ &\equiv \forall x\, P(x) \land \neg\exists x\, Q(x)\\ &\equiv \forall x\, P(x) \land \forall x\, \neg Q(x) \end{aligned} \] using the equivalences: \( A \to B \equiv \neg A \lor B \), De Morgan's law, and \( \neg\exists x\, Q(x) \equiv \forall x\, \neg Q(x) \).
Q4
Structural Induction on Regular Expressions
5 pts
Let \( \Sigma = \{a, b\} \). For a regular expression \( R \) over \( \Sigma \), define \( \#_a(R) \) as
the number of occurrences of the symbol \( a \) in \( R \) (counting \( a \) in the regex syntax, not in
the language).
Prove by structural induction that for any regular expressions \( R \) and \( S \): \[ \#_a(R + S) = \#_a(R) + \#_a(S) \] \[ \#_a(R \cdot S) = \#_a(R) + \#_a(S) \] \[ \#_a(R^*) = \#_a(R) \]
Prove by structural induction that for any regular expressions \( R \) and \( S \): \[ \#_a(R + S) = \#_a(R) + \#_a(S) \] \[ \#_a(R \cdot S) = \#_a(R) + \#_a(S) \] \[ \#_a(R^*) = \#_a(R) \]
Solution:
We prove by structural induction on the construction of regular expressions.
Base Cases: For atomic regex \( \emptyset, \varepsilon, a, b \), the properties hold trivially (count the \( a \)'s directly).
Inductive Cases: Assume properties hold for \( R \) and \( S \).
Union: \( \#_a(R + S) \) counts all \( a \)'s appearing in the syntax of \( R \) plus all in \( S \), giving \( \#_a(R) + \#_a(S) \).
Concatenation: \( \#_a(R \cdot S) \) counts all \( a \)'s in \( R \) and \( S \) without adding new ones, giving \( \#_a(R) + \#_a(S) \).
Kleene Star: \( \#_a(R^*) \) adds only the \( * \) symbol to \( R \), preserving the count: \( \#_a(R^*) = \#_a(R) \).
Base Cases: For atomic regex \( \emptyset, \varepsilon, a, b \), the properties hold trivially (count the \( a \)'s directly).
Inductive Cases: Assume properties hold for \( R \) and \( S \).
Union: \( \#_a(R + S) \) counts all \( a \)'s appearing in the syntax of \( R \) plus all in \( S \), giving \( \#_a(R) + \#_a(S) \).
Concatenation: \( \#_a(R \cdot S) \) counts all \( a \)'s in \( R \) and \( S \) without adding new ones, giving \( \#_a(R) + \#_a(S) \).
Kleene Star: \( \#_a(R^*) \) adds only the \( * \) symbol to \( R \), preserving the count: \( \#_a(R^*) = \#_a(R) \).
Q5
Divisibility and Proof by Cases
5 pts
Prove that for any integer \( n \), the expression \( n^5 - n \) is divisible by 30.
Hint: Factor the expression and use proof by cases considering \( n \bmod 2, 3, 5 \).
Hint: Factor the expression and use proof by cases considering \( n \bmod 2, 3, 5 \).
Solution:
Factor: \( n^5 - n = n(n-1)(n+1)(n^2+1) \).
Since \( 30 = 2 \cdot 3 \cdot 5 \), we verify divisibility by each prime:
By 2: Among three consecutive integers \( n-1, n, n+1 \), one is even.
By 3: Considering \( n \bmod 3 \):
By 5: Considering \( n \bmod 5 \):
Therefore \( 2 \cdot 3 \cdot 5 = 30 \) divides \( n^5 - n \).
Since \( 30 = 2 \cdot 3 \cdot 5 \), we verify divisibility by each prime:
By 2: Among three consecutive integers \( n-1, n, n+1 \), one is even.
By 3: Considering \( n \bmod 3 \):
- \( n \equiv 0 \): then \( 3 \mid n \)
- \( n \equiv 1 \): then \( 3 \mid (n-1) \)
- \( n \equiv 2 \): then \( 3 \mid (n+1) \)
By 5: Considering \( n \bmod 5 \):
- \( n \equiv 0 \): then \( 5 \mid n \)
- \( n \equiv \pm 1 \): then \( 5 \mid (n \mp 1) \)
- \( n \equiv \pm 2 \): then \( n^2 \equiv 4 \pmod{5} \), so \( 5 \mid (n^2+1) \)
Therefore \( 2 \cdot 3 \cdot 5 = 30 \) divides \( n^5 - n \).
Q6
String Properties - Missing Steps
5 pts
Consider the proof that for any strings \( w, x \in \Sigma^* \), we have \( |wx| = |w| + |x| \).
The proof proceeds by induction on the length of \( x \). Complete the missing steps:
Proof: We prove by induction on \( |x| \).
Base Case: When \( |x| = 0 \), we have \( x = \varepsilon \). \(\_\_\_\_\_\) (Step 1) Therefore, \( |w\varepsilon| = |w| = |w| + 0 = |w| + |\varepsilon| \). ✓
Inductive Step: Assume \( |wy| = |w| + |y| \) for all strings \( w \) and all strings \( y \) with \( |y| = k \).
Consider a string \( x \) with \( |x| = k+1 \). We can write \( x = ya \) where \( |y| = k \) and \( a \in \Sigma \). Then: \[ |wx| = |w(ya)| = \_\_\_\_\_\_\_\_\_\_ \textbf{(Step 2)} \] By the inductive hypothesis: \[ = \_\_\_\_\_\_\_\_\_\_ \textbf{(Step 3)} \] By definition of string length: \[ = \_\_\_\_\_\_\_\_\_\_ \textbf{(Step 4)} \] Since \( |x| = |ya| = |y| + 1 = k + 1 \), we have shown \( |wx| = |w| + |x| \).
Proof: We prove by induction on \( |x| \).
Base Case: When \( |x| = 0 \), we have \( x = \varepsilon \). \(\_\_\_\_\_\) (Step 1) Therefore, \( |w\varepsilon| = |w| = |w| + 0 = |w| + |\varepsilon| \). ✓
Inductive Step: Assume \( |wy| = |w| + |y| \) for all strings \( w \) and all strings \( y \) with \( |y| = k \).
Consider a string \( x \) with \( |x| = k+1 \). We can write \( x = ya \) where \( |y| = k \) and \( a \in \Sigma \). Then: \[ |wx| = |w(ya)| = \_\_\_\_\_\_\_\_\_\_ \textbf{(Step 2)} \] By the inductive hypothesis: \[ = \_\_\_\_\_\_\_\_\_\_ \textbf{(Step 3)} \] By definition of string length: \[ = \_\_\_\_\_\_\_\_\_\_ \textbf{(Step 4)} \] Since \( |x| = |ya| = |y| + 1 = k + 1 \), we have shown \( |wx| = |w| + |x| \).
Solution:
Step 1: \( w\varepsilon = w \) (definition of empty string concatenation)
Step 2: \( |(wy)a| \) (associativity of concatenation)
Step 3: \( |wy| + |a| = (|w| + |y|) + 1 \) (inductive hypothesis, \( |a| = 1 \))
Step 4: \( |w| + |y| + 1 = |w| + (|y| + 1) = |w| + |x| \) (since \( |x| = |ya| = |y| + 1 \))
Step 2: \( |(wy)a| \) (associativity of concatenation)
Step 3: \( |wy| + |a| = (|w| + |y|) + 1 \) (inductive hypothesis, \( |a| = 1 \))
Step 4: \( |w| + |y| + 1 = |w| + (|y| + 1) = |w| + |x| \) (since \( |x| = |ya| = |y| + 1 \))
Q7
Resolution Proof System
5 pts
Using only the Resolution rule (from \( p \lor q \) and \( \neg p \lor r \), infer \( q
\lor r \)), prove that the following set of clauses is unsatisfiable:
\[ \{p \lor q, \, \neg p \lor r, \, \neg q \lor s, \, \neg r \lor s, \, \neg s\} \]
Show each resolution step clearly, indicating which clauses are being resolved.
Solution:
Given: \( \{p \lor q,\, \neg p \lor r,\, \neg q \lor s,\, \neg r \lor s,\, \neg s\} \)
\[ \begin{aligned} (1) \land (2) &\implies q \lor r && \text{(resolve on } p) \\ (q \lor r) \land (3) &\implies r \lor s && \text{(resolve on } q) \\ (r \lor s) \land (4) &\implies s && \text{(resolve on } r) \\ s \land (5) &\implies \square && \text{(resolve on } s) \end{aligned} \] The empty clause proves unsatisfiability.
\[ \begin{aligned} (1) \land (2) &\implies q \lor r && \text{(resolve on } p) \\ (q \lor r) \land (3) &\implies r \lor s && \text{(resolve on } q) \\ (r \lor s) \land (4) &\implies s && \text{(resolve on } r) \\ s \land (5) &\implies \square && \text{(resolve on } s) \end{aligned} \] The empty clause proves unsatisfiability.