1. Problem: Solve the recurrence relation $a_n = 8a_{n-1} - 16a_{n-2}$ for $n \ge 2$ with initial conditions $a_0 = 16$ and $a_1 = 80$. Step 1: Write the characteristic equation associated with the recurrence: $$r^2 - 8r + 16 = 0$$ Step 2: Solve the quadratic: $$r = \frac{8 \pm \sqrt{64 - 64}}{2} = \frac{8}{2} = 4$$ Since the root $r=4$ is repeated twice, the general solution is: $$a_n = (A + Bn)4^n$$ Step 3: Use initial conditions to find $A$ and $B$. - For $n=0$, $$a_0 = 16 = A \cdot 4^0 = A \Rightarrow A = 16$$ - For $n=1$, $$a_1 = 80 = (16 + B \cdot 1)4^1 = 4(16 + B) = 64 + 4B \Rightarrow 4B = 16 \Rightarrow B=4$$ Step 4: Final solution: $$a_n = (16 + 4n)4^n$$ 2. Problem: Solve the recurrence relation $a_n = -3a_{n-1} - 3a_{n-2} - a_{n-3}$ with $a_0 = 5$, $a_1 = -9$, $a_2 = 15$. Step 1: Write characteristic equation: $$r^3 + 3r^2 +3r + 1=0$$ This factors as: $$(r+1)^3 = 0$$ Step 2: The root $r=-1$ has multiplicity 3, so general solution: $$a_n = (A + Bn + Cn^2)(-1)^n$$ Step 3: Use initial conditions: - $n=0$: $$a_0=5 = A$$ - $n=1$: $$a_1=-9 = (A + B + C)(-1) = - (5 + B + C) \Rightarrow 5 + B + C = 9 \Rightarrow B + C = 4$$ - $n=2$: $$a_2=15 = (A + 2B + 4C)(-1)^2 = 5 + 2B + 4C$$ So: $$5 + 2B + 4C =15 \Rightarrow 2B + 4C = 10$$ Step 4: Solve system From $B+C=4$ multiply by 2: $$2B + 2C = 8$$ Subtract from $2B + 4C=10$: $$ (2B + 4C) - (2B + 2C) = 10 - 8 \Rightarrow 2C = 2 \Rightarrow C=1$$ From $B + C=4$, $$B = 4 -1 =3$$ Step 5: Final solution: $$a_n = (5 + 3n + n^2)(-1)^n$$ 3. Problem: Solve $y_{n+2} - 4y_{n+1} + 3y_n = 0$ with $y_0=2$, $y_1=4$ using the generating function. Step 1: Let generating function be $$G(x) = \sum_{n=0}^\infty y_n x^n$$ Step 2: Use the recurrence to relate $G(x)$: $$\sum_{n=0}^\infty y_{n+2}x^n - 4 \sum_{n=0}^\infty y_{n+1} x^n + 3 \sum_{n=0}^\infty y_n x^n = 0$$ Shift indices: $$\frac{G(x) - y_0 - y_1 x}{x^2} - 4 \frac{G(x) - y_0}{x} + 3G(x) = 0$$ Multiply both sides by $x^2$: $$G(x) - y_0 - y_1 x - 4x(G(x) - y_0) + 3x^2 G(x) = 0$$ Step 3: Substitute $y_0=2$, $y_1=4$: $$G(x) - 2 - 4x - 4xG(x) + 8x + 3x^2 G(x) = 0$$ Group terms: $$(1 - 4x + 3x^2) G(x) = 2 + 4x - 8x = 2 - 4x$$ Step 4: Solve for $G(x)$: $$G(x) = \frac{2 - 4x}{1 - 4x + 3x^2}$$ Step 5: Partial fraction decompose denominator: $$1 - 4x + 3x^2 = (1 - x)(1 - 3x)$$ Step 6: Write: $$G(x) = \frac{2 - 4x}{(1 - x)(1 - 3x)} = \frac{A}{1 - x} + \frac{B}{1 - 3x}$$ Solve for $A$ and $B$: Multiply both sides by $(1-x)(1-3x)$: $$2 - 4x = A(1 - 3x) + B(1 - x)$$ Set $x=1$: $$2 - 4(1) = A(1 -3) + B(0) \Rightarrow -2 = -2A \Rightarrow A=1$$ Set $x= \frac{1}{3}$: $$2 - 4\cdot \frac{1}{3} = A(1 - 1) + B(1 - \frac{1}{3}) \Rightarrow 2 - \frac{4}{3} = 0 + B \frac{2}{3} \Rightarrow \frac{2}{3} = \frac{2}{3} B \Rightarrow B=1$$ Step 7: So $$G(x) = \frac{1}{1-x} + \frac{1}{1-3x} = \sum_{n=0}^\infty (1 + 3^n) x^n$$ Step 8: From generating function, $$y_n = 1 + 3^n$$ Step 9: Check initial conditions: - $n=0: y_0 = 1 + 3^0 = 2$ - $n=1: y_1 = 1 + 3 = 4$ Correct. 4. Problem: State and prove Ore's Theorem. Step 1: Statement: If $G$ is a simple graph on $n \ge 3$ vertices, and for every pair of nonadjacent vertices $u,v$, $$\deg(u) + \deg(v) \ge n,$$ then $G$ is Hamiltonian (contains a cycle passing through all vertices). Step 2: Proof (Outline): - Assume contrary, $G$ not Hamiltonian. - Add edges between nonadjacent vertices $u,v$ to satisfy degree condition. - Show adding such edges creates longer cycles. - Reaching contradiction implies $G$ must contain Hamiltonian cycle. (The complete proof uses contradiction and closure properties of graphs, see standard graph theory texts).