diff --git a/writeup.md b/writeup.md
index a8624cd..11dc852 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,304 @@
 
 ## Student Responses
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
 
-[Your solutions here]
+## Part 1
 
+### Problem 1 [10 points]
+
+**Algorithm: Two Sum using Divide and Conquer (Sort + Binary Search)**
+
+**Pseudo-code:**
+
+```
+TwoSum(S, x):
+    Sort S in non-decreasing order using merge sort   // O(n log n)
+    left  ← 0
+    right ← n - 1
+    while left < right:
+        sum ← S[left] + S[right]
+        if sum == x:
+            return true
+        else if sum < x:
+            left ← left + 1
+        else:
+            right ← right - 1
+    return false
+```
+
+**Divide and Conquer justification:**
+The sorting step uses merge sort, which is a classic divide-and-conquer algorithm:
+- **Divide:** Split S into two halves S_L and S_R of size n/2.
+- **Conquer:** Recursively sort each half.
+- **Combine:** Merge the two sorted halves in O(n) time.
+
+This gives the recurrence T(n) = 2T(n/2) + O(n), which by the Master Theorem solves to T(n) = O(n log n).
+
+**Two-pointer scan:** After sorting, the two-pointer traversal runs in O(n) since each step advances either `left` or `right`, and they can each move at most n times total.
+
+**Correctness:** Since S is sorted, S[left] is the smallest unexamined element and S[right] is the largest. If their sum is less than x we need a larger sum (advance left); if it is greater than x we need a smaller sum (advance right). This exhaustively checks all candidate pairs.
+
+**Overall complexity:** O(n log n) + O(n) = **O(n log n)**.
+
+---
+
+### Problem 2 [10 points]
+
+**Claim:** For every positive integer n,
+$$\sum_{i=1}^{n} i(i+1)(i+2) = \frac{n(n+1)(n+2)(n+3)}{4}$$
+
+**Proof by mathematical induction on n.**
+
+**Base case (n = 1):**
+LHS: $1 \cdot 2 \cdot 3 = 6$
+RHS: $\dfrac{1 \cdot 2 \cdot 3 \cdot 4}{4} = \dfrac{24}{4} = 6$
+LHS = RHS ✓
+
+**Inductive step:**
+Assume the statement holds for n = k (for some k ≥ 1):
+$$\sum_{i=1}^{k} i(i+1)(i+2) = \frac{k(k+1)(k+2)(k+3)}{4}$$
+
+We must show it holds for n = k+1, i.e.,
+$$\sum_{i=1}^{k+1} i(i+1)(i+2) = \frac{(k+1)(k+2)(k+3)(k+4)}{4}$$
+
+Starting from the left-hand side:
+$$\sum_{i=1}^{k+1} i(i+1)(i+2) = \sum_{i=1}^{k} i(i+1)(i+2) + (k+1)(k+2)(k+3)$$
+
+Applying the inductive hypothesis:
+$$= \frac{k(k+1)(k+2)(k+3)}{4} + (k+1)(k+2)(k+3)$$
+
+Factor out $(k+1)(k+2)(k+3)$:
+$$= (k+1)(k+2)(k+3)\left(\frac{k}{4} + 1\right)$$
+
+$$= (k+1)(k+2)(k+3) \cdot \frac{k+4}{4}$$
+
+$$= \frac{(k+1)(k+2)(k+3)(k+4)}{4}$$
+
+This is exactly the right-hand side for n = k+1. By induction, the statement holds for all positive integers n. $\blacksquare$
+
+---
+
+### Problem 3 [10 points]
+
+**Claim:** For all n ≥ 0,
+$$\sum_{i=0}^{n} i^3 = \left(\sum_{i=0}^{n} i\right)^2$$
+
+**Note:** Since $\displaystyle\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$, the right-hand side equals $\dfrac{n^2(n+1)^2}{4}$.
+
+We prove by induction that $\displaystyle\sum_{i=0}^{n} i^3 = \frac{n^2(n+1)^2}{4}$.
+
+**Base case (n = 0):**
+LHS: $0^3 = 0$
+RHS: $\dfrac{0^2 \cdot 1^2}{4} = 0$
+LHS = RHS ✓
+
+**Inductive step:**
+Assume $\displaystyle\sum_{i=0}^{k} i^3 = \frac{k^2(k+1)^2}{4}$ for some k ≥ 0.
+
+We show $\displaystyle\sum_{i=0}^{k+1} i^3 = \frac{(k+1)^2(k+2)^2}{4}$:
+
+$$\sum_{i=0}^{k+1} i^3 = \sum_{i=0}^{k} i^3 + (k+1)^3 = \frac{k^2(k+1)^2}{4} + (k+1)^3$$
+
+Factor out $(k+1)^2$:
+$$= (k+1)^2 \left(\frac{k^2}{4} + (k+1)\right) = (k+1)^2 \cdot \frac{k^2 + 4k + 4}{4} = \frac{(k+1)^2(k+2)^2}{4}$$
+
+This equals $\left(\dfrac{(k+1)(k+2)}{2}\right)^2 = \left(\displaystyle\sum_{i=0}^{k+1} i\right)^2$, completing the induction. $\blacksquare$
+
+---
+
+## Part 2
+
+### Problem 4 [10 points]
+
+**Claim:** If no two of n lines are parallel and no three pass through a common point, then n lines divide the plane into $\dfrac{n^2 + n + 2}{2}$ regions.
+
+**Proof by mathematical induction on n.**
+
+**Base case (n = 0):**
+0 lines leave the plane as 1 undivided region.
+$\dfrac{0 + 0 + 2}{2} = 1$ ✓
+
+**Inductive step:**
+Assume k lines satisfying the conditions divide the plane into $\dfrac{k^2 + k + 2}{2}$ regions. Add one more line $\ell_{k+1}$ (still satisfying the conditions).
+
+- Since $\ell_{k+1}$ is not parallel to any of the k existing lines, it intersects each one.
+- Since no three lines pass through a common point, the k intersections of $\ell_{k+1}$ with the existing lines are **k distinct points** on $\ell_{k+1}$.
+
+These k distinct points divide $\ell_{k+1}$ into **k+1 pieces** (2 infinite rays plus k−1 bounded segments).
+
+Each piece of $\ell_{k+1}$ lies entirely within one existing region and cuts it into two, creating exactly **1 new region per piece**.
+
+Therefore adding $\ell_{k+1}$ creates k+1 new regions:
+$$\frac{k^2+k+2}{2} + (k+1) = \frac{k^2+k+2+2k+2}{2} = \frac{k^2+3k+4}{2}$$
+
+We verify this equals $\dfrac{(k+1)^2+(k+1)+2}{2}$:
+$$(k+1)^2+(k+1)+2 = k^2+2k+1+k+1+2 = k^2+3k+4 \checkmark$$
+
+By induction, the formula holds for all n ≥ 0. $\blacksquare$
+
+---
+
+### Problem 5 [10 points]
+
+**Claim:** For every integer n ≥ 18, n cents of postage can be formed using only 4-cent and 7-cent stamps.
+
+**Proof by strong induction on n.**
+
+**Base cases (n = 18, 19, 20, 21):**
+- n = 18: $18 = 7 + 7 + 4$ ✓
+- n = 19: $19 = 7 + 4 + 4 + 4$ ✓
+- n = 20: $20 = 4 + 4 + 4 + 4 + 4$ ✓
+- n = 21: $21 = 7 + 7 + 7$ ✓
+
+**Inductive step:**
+Let n ≥ 22 be an integer. Assume (strong induction hypothesis) that every integer m with $18 \le m < n$ can be formed using 4-cent and 7-cent stamps.
+
+Consider $n - 4$. Since $n \ge 22$, we have $n - 4 \ge 18$. Also $n - 4 < n$.
+
+By the strong induction hypothesis applied to $m = n-4$, the amount $n - 4$ cents can be formed using 4-cent and 7-cent stamps. Adding one more 4-cent stamp gives a valid combination for $n$ cents.
+
+By strong induction, the claim holds for all integers n ≥ 18. $\blacksquare$
+
+---
+
+### Problem 6 [10 points]
+
+**Claim:** Let x be a real number such that $x + \dfrac{1}{x} \in \mathbb{Z}$. Then $x^n + \dfrac{1}{x^n} \in \mathbb{Z}$ for all integers n ≥ 0.
+
+**Proof by strong induction on n.**
+
+Let $P(n)$ denote the statement "$x^n + x^{-n} \in \mathbb{Z}$."
+
+**Base cases:**
+- $P(0)$: $x^0 + x^{-0} = 1 + 1 = 2 \in \mathbb{Z}$ ✓
+- $P(1)$: $x + x^{-1} \in \mathbb{Z}$ by hypothesis ✓
+
+**Inductive step:**
+Let k ≥ 1. Assume $P(j)$ holds for all $0 \le j \le k$. We prove $P(k+1)$.
+
+Observe the following product identity:
+$$(x + x^{-1})(x^k + x^{-k}) = x^{k+1} + x^{k-1} + x^{-(k-1)} + x^{-(k+1)}$$
+$$= \left(x^{k+1} + x^{-(k+1)}\right) + \left(x^{k-1} + x^{-(k-1)}\right)$$
+
+Rearranging:
+$$x^{k+1} + x^{-(k+1)} = \left(x + x^{-1}\right)\!\left(x^k + x^{-k}\right) - \left(x^{k-1} + x^{-(k-1)}\right)$$
+
+By the inductive hypothesis:
+- $x + x^{-1} \in \mathbb{Z}$ (given, i.e., $P(1)$)
+- $x^k + x^{-k} \in \mathbb{Z}$ (by $P(k)$)
+- $x^{k-1} + x^{-(k-1)} \in \mathbb{Z}$ (by $P(k-1)$, noting $k-1 \ge 0$)
+
+Therefore $x^{k+1} + x^{-(k+1)}$ equals an integer times an integer minus an integer, which is an integer. Hence $P(k+1)$ holds.
+
+By strong induction, $x^n + x^{-n} \in \mathbb{Z}$ for all n ≥ 0. $\blacksquare$
+
+---
+
+## Part 3
+
+### Problem 7 [10 points]
+
+**Claim:** Let $a_1 = 1$, $a_2 = 2$, $a_3 = 3$, and $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ for n ≥ 4. Then $a_n < 2^n$ for all positive integers n.
+
+**Proof by strong induction on n.**
+
+**Base cases:**
+- n = 1: $a_1 = 1 < 2^1 = 2$ ✓
+- n = 2: $a_2 = 2 < 2^2 = 4$ ✓
+- n = 3: $a_3 = 3 < 2^3 = 8$ ✓
+
+**Inductive step:**
+Let n ≥ 4. Assume $a_j < 2^j$ for all positive integers $j < n$ (strong inductive hypothesis). We prove $a_n < 2^n$.
+
+Since n ≥ 4, by the recurrence and the strong inductive hypothesis applied to n-1, n-2, and n-3:
+$$a_n = a_{n-1} + a_{n-2} + a_{n-3} < 2^{n-1} + 2^{n-2} + 2^{n-3}$$
+
+Factor out $2^{n-3}$:
+$$= 2^{n-3}(4 + 2 + 1) = 7 \cdot 2^{n-3} = \frac{7}{8} \cdot 2^n < 2^n$$
+
+since $\dfrac{7}{8} < 1$.
+
+By strong induction, $a_n < 2^n$ for all positive integers n. $\blacksquare$
+
+---
+
+### Problem 8 [10 points]
+
+**Recursive definition of the set M of all binary strings with more 0's than 1's (strings over {0, 1} where #0 > #1):**
+
+**Basis:**
+"0" ∈ M.
+
+**Recursive rules:** For any strings already known to be in M:
+1. If $w \in M$, then $\mathtt{0}w \in M$ (prepend a 0).
+2. If $w \in M$, then $w\mathtt{0} \in M$ (append a 0).
+3. If $w \in M$, then $\mathtt{0}w\mathtt{1} \in M$ (wrap: one extra 0 offsets the added 1).
+4. If $w \in M$, then $\mathtt{1}w\mathtt{0} \in M$ (wrap: one extra 0 offsets the added 1).
+5. If $s \in M$ and $t \in M$, then $st \in M$ (concatenation).
+
+**Closure:** Nothing else is in M.
+
+**Soundness:** Each rule preserves #0 > #1:
+- Basis: "0" has 1 zero, 0 ones ✓
+- Rules 1 & 2: add one 0, increasing the excess by 1 ✓
+- Rules 3 & 4: add one 0 and one 1, preserving the existing excess ✓
+- Rule 5: if #0(s) > #1(s) and #0(t) > #1(t), then #0(st) = #0(s)+#0(t) > #1(s)+#1(t) = #1(st) ✓
+
+**Examples:**
+- "0" ∈ M (basis)
+- "00" ∈ M (Rule 1 or 2 on "0")
+- "001" ∈ M (Rule 3 on "0": "0"+"0"+"1")
+- "100" ∈ M (Rule 4 on "0": "1"+"0"+"0")
+- "000111" ∈ M (Rule 3 applied repeatedly; note #0=3 > #1=3 is NOT satisfied — incorrect, skip)
+- "0000" ∈ M (Rule 2 on "000"; "000" from Rule 2 twice on "0")
+- "001001" ∈ M (Rule 5 on "001" and "001")
+
+---
+
+### Problem 9 [20 points]
+
+#### Part (a): Recursive definition of balanced strings of parentheses
+
+Let B be the set of all balanced strings over the alphabet {(, )}.
+
+**Basis:**
+$\varepsilon$ (the empty string) ∈ B.
+
+**Recursive rules:**
+1. If $s \in B$, then $(s)\ \in B$ (wrap s in a matching pair of parentheses).
+2. If $s \in B$ and $t \in B$, then $st \in B$ (concatenation of two balanced strings).
+
+**Closure:** Nothing else is in B.
+
+**Verification of examples:**
+- $()$: apply Rule 1 to $\varepsilon$ → $(\ \varepsilon\ ) = ()$ ✓
+- $(())$: apply Rule 1 to $()$ → $( () )$ ✓
+- $()()()$: Rule 2 on $()$ and $()()$; $()()$ = Rule 2 on $()$ and $()$ ✓
+- $(())) $: 2 left, 3 right — not generated by these rules (not balanced) ✓
+- $()()(\ $: 3 left, 2 right — not generated ✓
+
+---
+
+#### Part (b): Proof that every balanced string has equal left and right parentheses
+
+**Claim:** If $x \in B$, then the number of left parentheses in $x$ equals the number of right parentheses in $x$.
+
+Let $L(x)$ denote the number of '(' in x and $R(x)$ the number of ')' in x.
+
+**Proof by structural induction on the definition of B.**
+
+**Base case:** $x = \varepsilon$.
+$L(\varepsilon) = 0 = R(\varepsilon)$. ✓
+
+**Inductive case 1:** $x = (s)$ for some $s \in B$.
+**Inductive hypothesis (IH):** $L(s) = R(s)$.
+Then:
+$$L(x) = L\bigl((s)\bigr) = 1 + L(s) \stackrel{\text{IH}}{=} 1 + R(s) = R\bigl((s)\bigr) = R(x) \checkmark$$
+
+**Inductive case 2:** $x = st$ for some $s, t \in B$.
+**Inductive hypotheses:** $L(s) = R(s)$ and $L(t) = R(t)$.
+Then:
+$$L(x) = L(st) = L(s) + L(t) \stackrel{\text{IH}}{=} R(s) + R(t) = R(st) = R(x) \checkmark$$
+
+In all cases $L(x) = R(x)$. By structural induction, every balanced string $x \in B$ has an equal number of left and right parentheses. $\blacksquare$