diff --git a/writeup.md b/writeup.md
index a8624cd..3dadfba 100644
--- a/writeup.md
+++ b/writeup.md
@@ -2,8 +2,429 @@
 
 ## Student Responses
 
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
 
-[Your solutions here]
+## Problem 1 [10 points]
 
+**Algorithm:** Two-Sum via Divide and Conquer
+
+The key idea is to sort the array using merge sort (a divide and conquer algorithm) and then use a two-pointer scan.
+
+**Pseudocode:**
+
+```
+TwoSum(S, x):
+    A = MergeSort(S)          // O(n log n), divide and conquer
+    left = 0
+    right = n - 1
+    while left < right:
+        sum = A[left] + A[right]
+        if sum == x:
+            return true
+        else if sum < x:
+            left = left + 1
+        else:
+            right = right - 1
+    return false
+```
+
+**Alternatively**, we can phrase the entire algorithm in a purely divide-and-conquer fashion. The idea is to combine sorting with the search, analogous to merge sort:
+
+```
+TwoSumDC(S, x):
+    if |S| <= 1:
+        return (S_sorted = S, false)
+
+    Split S into two halves L, R of size floor(n/2) and ceil(n/2)
+
+    (L_sorted, foundL) = TwoSumDC(L, x)
+    (R_sorted, foundR) = TwoSumDC(R, x)
+
+    if foundL or foundR:
+        merged = Merge(L_sorted, R_sorted)
+        return (merged, true)
+
+    // Check cross-pairs: one element from L, one from R
+    // Both L_sorted and R_sorted are sorted
+    i = 0, j = |R_sorted| - 1
+    foundCross = false
+    while i < |L_sorted| and j >= 0:
+        sum = L_sorted[i] + R_sorted[j]
+        if sum == x:
+            foundCross = true
+            break
+        else if sum < x:
+            i = i + 1
+        else:
+            j = j - 1
+
+    merged = Merge(L_sorted, R_sorted)    // Standard merge in O(n)
+    return (merged, foundCross)
+```
+
+Call `TwoSumDC(S, x)` and return the boolean component.
+
+**Complexity Analysis:**
+
+The recurrence for this algorithm is:
+
+T(n) = 2T(n/2) + O(n)
+
+- **Divide:** Split S into two halves — O(1).
+- **Conquer:** Recursively solve both halves — 2T(n/2).
+- **Combine:** The cross-pair check uses two pointers on sorted halves — O(n). The merge step is also O(n). Total combine cost: O(n).
+
+By the Master Theorem (Case 2, with a = 2, b = 2, f(n) = O(n), so n^(log_b a) = n^1 = n = f(n)):
+
+**T(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 induction on n.**
+
+**Base case (n = 1):**
+
+LHS = 1(2)(3) = 6
+
+RHS = 1(2)(3)(4) / 4 = 24/4 = 6
+
+LHS = RHS. The base case holds.
+
+**Inductive step:**
+
+Assume the formula holds for some positive integer k, i.e.,
+
+$$\sum_{i=1}^{k} i(i+1)(i+2) = \frac{k(k+1)(k+2)(k+3)}{4}$$
+
+We must show it holds for k + 1:
+
+$$\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)$$
+
+Factoring 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 formula with n = k + 1.
+
+By the principle of mathematical induction, the formula 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$.
+
+Using the well-known identity $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$, this is equivalent to proving:
+
+$$\sum_{i=0}^{n} i^3 = \frac{n^2(n+1)^2}{4}$$
+
+**Proof by induction on n.**
+
+**Base case (n = 0):**
+
+LHS = 0^3 = 0
+
+RHS = (0)^2 = 0
+
+LHS = RHS. The base case holds.
+
+**Base case (n = 1):**
+
+LHS = 0^3 + 1^3 = 1
+
+RHS = (0 + 1)^2 = 1
+
+LHS = RHS. This case also holds.
+
+**Inductive step:**
+
+Assume the formula holds for some non-negative integer k:
+
+$$\sum_{i=0}^{k} i^3 = \frac{k^2(k+1)^2}{4}$$
+
+We must show:
+
+$$\sum_{i=0}^{k+1} i^3 = \frac{(k+1)^2(k+2)^2}{4}$$
+
+Starting from the left-hand side:
+
+$$\sum_{i=0}^{k+1} i^3 = \sum_{i=0}^{k} i^3 + (k+1)^3$$
+
+Applying the inductive hypothesis:
+
+$$= \frac{k^2(k+1)^2}{4} + (k+1)^3$$
+
+Factoring 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}$$
+
+$$= (k+1)^2 \cdot \frac{(k+2)^2}{4}$$
+
+$$= \frac{(k+1)^2(k+2)^2}{4}$$
+
+This is exactly the formula with n = k + 1, which equals $\left(\sum_{i=0}^{k+1} i\right)^2 = \left(\frac{(k+1)(k+2)}{2}\right)^2$.
+
+By the principle of mathematical induction, the identity holds for all n >= 0. $\blacksquare$
+
+---
+
+## Problem 4 [10 points]
+
+**Claim:** If n lines are drawn in the plane such that no two are parallel and no three pass through a common point, then they separate the plane into $\frac{n^2 + n + 2}{2}$ regions.
+
+**Proof by induction on n.**
+
+**Base case (n = 0):**
+
+With 0 lines, the plane has 1 region.
+
+Formula: $(0^2 + 0 + 2)/2 = 2/2 = 1$. The base case holds.
+
+**Base case (n = 1):**
+
+With 1 line, the plane is divided into 2 regions.
+
+Formula: $(1 + 1 + 2)/2 = 4/2 = 2$. This case also holds.
+
+**Inductive step:**
+
+Assume that k lines (with no two parallel and no three concurrent) divide the plane into $\frac{k^2 + k + 2}{2}$ regions.
+
+Now add the $(k+1)$-th line. We need to show the total number of regions becomes $\frac{(k+1)^2 + (k+1) + 2}{2}$.
+
+Since no two lines are parallel, the new line intersects each of the existing k lines. Since no three lines pass through a common point, all k intersection points are distinct.
+
+These k distinct intersection points divide the $(k+1)$-th line into $k + 1$ segments (k - 1 finite segments between consecutive intersection points, plus 2 unbounded rays at the ends).
+
+Each of these $k + 1$ segments passes through the interior of a distinct region, splitting that region into two parts. Therefore, the new line adds exactly $k + 1$ new regions.
+
+The new total number of regions is:
+
+$$\frac{k^2 + k + 2}{2} + (k + 1) = \frac{k^2 + k + 2 + 2(k + 1)}{2} = \frac{k^2 + k + 2 + 2k + 2}{2} = \frac{k^2 + 3k + 4}{2}$$
+
+We verify: $(k+1)^2 + (k+1) + 2 = k^2 + 2k + 1 + k + 1 + 2 = k^2 + 3k + 4$.
+
+So the new total is $\frac{(k+1)^2 + (k+1) + 2}{2}$, as required.
+
+By the principle of mathematical induction, the formula holds for all n >= 0. $\blacksquare$
+
+---
+
+## Problem 5 [10 points]
+
+**Claim:** For all integers n >= 18, a postage of n cents can be formed using only 4-cent and 7-cent stamps.
+
+**Proof by strong induction on n.**
+
+**Base cases:**
+
+- n = 18: 18 = 4(1) + 7(2) = 4 + 14 ✓
+- n = 19: 19 = 4(3) + 7(1) = 12 + 7 ✓
+- n = 20: 20 = 4(5) + 7(0) = 20 ✓
+- n = 21: 21 = 4(0) + 7(3) = 21 ✓
+
+**Inductive step:**
+
+Let k >= 21 and assume that for all integers m with 18 <= m <= k, a postage of m cents can be formed using 4-cent and 7-cent stamps.
+
+We need to show that k + 1 cents can also be formed.
+
+Since k >= 21, we have k + 1 >= 22, so (k + 1) - 4 = k - 3 >= 18.
+
+By the inductive hypothesis (since 18 <= k - 3 <= k), the value k - 3 cents can be formed using 4-cent and 7-cent stamps.
+
+Therefore, (k + 1) cents can be formed by taking the stamps used for (k - 3) cents and adding one additional 4-cent stamp:
+
+$$k + 1 = (k - 3) + 4$$
+
+By the principle of strong induction, the claim holds for all n >= 18. $\blacksquare$
+
+---
+
+## Problem 6 [10 points]
+
+**Claim:** Let x be a real number such that $x + \frac{1}{x}$ is an integer. Then $x^n + \frac{1}{x^n}$ is an integer for all integers n >= 0.
+
+**Proof by strong induction on n.**
+
+**Base cases:**
+
+- n = 0: $x^0 + \frac{1}{x^0} = 1 + 1 = 2$, which is an integer. ✓
+- n = 1: $x^1 + \frac{1}{x^1} = x + \frac{1}{x}$, which is an integer by hypothesis. ✓
+
+**Inductive step:**
+
+Let n >= 1 and assume that $x^j + \frac{1}{x^j}$ is an integer for all $0 \leq j \leq n$. We need to show that $x^{n+1} + \frac{1}{x^{n+1}}$ is an integer.
+
+We use the following algebraic identity:
+
+$$\left(x^n + \frac{1}{x^n}\right)\left(x + \frac{1}{x}\right) = x^{n+1} + x^{n-1} + \frac{1}{x^{n-1}} + \frac{1}{x^{n+1}}$$
+
+$$= \left(x^{n+1} + \frac{1}{x^{n+1}}\right) + \left(x^{n-1} + \frac{1}{x^{n-1}}\right)$$
+
+Rearranging:
+
+$$x^{n+1} + \frac{1}{x^{n+1}} = \left(x^n + \frac{1}{x^n}\right)\left(x + \frac{1}{x}\right) - \left(x^{n-1} + \frac{1}{x^{n-1}}\right)$$
+
+By the inductive hypothesis:
+- $x^n + \frac{1}{x^n}$ is an integer (since $n \leq n$)
+- $x + \frac{1}{x}$ is an integer (given)
+- $x^{n-1} + \frac{1}{x^{n-1}}$ is an integer (since $0 \leq n - 1 \leq n$)
+
+The product of two integers is an integer, and the difference of two integers is an integer.
+
+Therefore, $x^{n+1} + \frac{1}{x^{n+1}}$ is an integer.
+
+By the principle of strong induction, the claim holds for all n >= 0. $\blacksquare$
+
+---
+
+## Problem 7 [10 points]
+
+**Claim:** For the sequence defined by $a_1 = 1$, $a_2 = 2$, $a_3 = 3$, and $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ for $n \geq 4$, we have $a_n < 2^n$ for all positive integers n.
+
+**Proof by strong induction on n.**
+
+**Base cases:**
+
+- n = 1: $a_1 = 1 < 2 = 2^1$ ✓
+- n = 2: $a_2 = 2 < 4 = 2^2$ ✓
+- n = 3: $a_3 = 3 < 8 = 2^3$ ✓
+
+**Inductive step:**
+
+Let n >= 3 and assume $a_j < 2^j$ for all $1 \leq j \leq n$. We need to show $a_{n+1} < 2^{n+1}$.
+
+Since $n + 1 \geq 4$, we can apply the recurrence:
+
+$$a_{n+1} = a_n + a_{n-1} + a_{n-2}$$
+
+By the inductive hypothesis (since $n-2, n-1, n$ are all between 1 and n):
+
+$$a_{n+1} < 2^n + 2^{n-1} + 2^{n-2}$$
+
+Factoring out $2^{n-2}$:
+
+$$a_{n+1} < 2^{n-2}(2^2 + 2^1 + 2^0) = 2^{n-2}(4 + 2 + 1) = 7 \cdot 2^{n-2}$$
+
+Since $7 < 8 = 2^3$:
+
+$$a_{n+1} < 2^3 \cdot 2^{n-2} = 2^{n+1}$$
+
+Therefore $a_{n+1} < 2^{n+1}$.
+
+By the principle of strong induction, $a_n < 2^n$ for all positive integers n. $\blacksquare$
+
+---
+
+## Problem 8 [10 points]
+
+**Recursive definition of the set S of all binary strings with more 0's than 1's:**
+
+**Basis:** The string "0" is in S.
+
+**Recursive rules:**
+
+1. If $w \in S$, then $0w \in S$ and $w0 \in S$.
+   *(Prepending or appending a 0 increases the excess of 0's over 1's by 1, so the string remains in S.)*
+
+2. If $w \in S$ and $w = uv$ for any binary strings $u, v$ (including $u = \varepsilon$ or $v = \varepsilon$), then $u01v \in S$ and $u10v \in S$.
+   *(Inserting the pair "01" or "10" at any position adds one 0 and one 1, preserving the excess of 0's over 1's.)*
+
+**Nothing else is in S.**
+
+**Justification of correctness:**
+
+*Every element of S has more 0's than 1's:* The basis element "0" has one 0 and zero 1's. Rule 1 adds a 0 (increasing the excess), and Rule 2 adds one 0 and one 1 (preserving the positive excess). So every generated string has more 0's than 1's.
+
+*Every binary string with more 0's than 1's is in S:* We argue by induction on the length of the string. The only length-1 string with more 0's is "0", which is in S by the basis. For a string $w$ of length > 1 with more 0's than 1's: if $w$ contains no 1's, it is a string of all 0's, which can be built from "0" by repeated application of Rule 1. If $w$ contains at least one 1, then $w$ must contain a substring "01" or "10" (since adjacent characters must differ somewhere). Removing this substring yields a shorter string $w'$ that still has more 0's than 1's. By induction, $w' \in S$, and $w$ is obtained from $w'$ by inserting "01" or "10" via Rule 2, so $w \in S$.
+
+---
+
+## Problem 9 [20 points]
+
+### Part (a): Recursive definition of balanced parentheses
+
+Let B denote the set of all balanced strings of parentheses.
+
+**Basis:** The empty string $\varepsilon$ is in B.
+
+**Recursive rules:**
+
+1. If $w \in B$, then $(w) \in B$.
+   *(Wrapping a balanced string in a matching pair of parentheses produces a balanced string.)*
+
+2. If $w_1 \in B$ and $w_2 \in B$, then $w_1 w_2 \in B$.
+   *(Concatenating two balanced strings produces a balanced string.)*
+
+**Nothing else is in B.**
+
+### Part (b): Proof that left parentheses equal right parentheses
+
+**Claim:** If $x$ is a balanced string of parentheses (i.e., $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 left parentheses "(" in $x$, and $R(x)$ the number of right parentheses ")" in $x$.
+
+**Proof by structural induction on the recursive definition of B.**
+
+**Base case:** $x = \varepsilon$ (the empty string).
+
+$L(\varepsilon) = 0 = R(\varepsilon)$.
+
+The base case holds.
+
+**Inductive step:**
+
+We consider the two recursive rules:
+
+**Case 1: $x = (w)$ where $w \in B$.**
+
+By the inductive hypothesis, $L(w) = R(w)$.
+
+Then:
+
+$$L(x) = L((w)) = 1 + L(w)$$
+$$R(x) = R((w)) = 1 + R(w)$$
+
+Since $L(w) = R(w)$:
+
+$$L(x) = 1 + L(w) = 1 + R(w) = R(x)$$
+
+So $L(x) = R(x)$.
+
+**Case 2: $x = w_1 w_2$ where $w_1, w_2 \in B$.**
+
+By the inductive hypothesis, $L(w_1) = R(w_1)$ and $L(w_2) = R(w_2)$.
+
+Then:
+
+$$L(x) = L(w_1 w_2) = L(w_1) + L(w_2)$$
+$$R(x) = R(w_1 w_2) = R(w_1) + R(w_2)$$
+
+Since $L(w_1) = R(w_1)$ and $L(w_2) = R(w_2)$:
+
+$$L(x) = L(w_1) + L(w_2) = R(w_1) + R(w_2) = R(x)$$
+
+So $L(x) = R(x)$.
+
+In both cases, the number of left parentheses equals the number of right parentheses.
+
+By the principle of structural induction, the property holds for all balanced strings of parentheses. $\blacksquare$