Let's solve each of these recurrence relations.

(a) $a_n = 3a_{n-1} - 2$, with $a_0 = 0$

This is a first-order linear recurrence relation. To solve it, we can use the method of homogeneous and particular solutions.

1. Homogeneous Solution: Solve $a_n^{(h)} = 3a_{n-1}^{(h)}$.

   • Assume $a_n^{(h)} = C \cdot 3^n$, where $C$ is a constant.

2. Particular Solution: Try a constant solution $a_n^{(p)} = A$.

   • Substitute into the recurrence: $A = 3A - 2$.
   • Solving, $A = 1$.

Thus, the general solution is: $a_n = C \cdot 3^n + 1$ Using $a_0 = 0$: $0 = C \cdot 3^0 + 1 \Rightarrow C = -1$ So, the solution is: $a_n = -3^n + 1$

(b) $a_n = 2a_{n-1} + (-1)^n$, with $a_0 = 2$

1. Homogeneous Solution: Solve $a_n^{(h)} = 2a_{n-1}^{(h)}$.

   • Assume $a_n^{(h)} = C \cdot 2^n$.

2. Particular Solution: Because of $(-1)^n$, try a solution of the form $a_n^{(p)} = A \cdot (-1)^n$.

   • Substitute into the recurrence: $A \cdot (-1)^n = 2A \cdot (-1)^{n-1} + (-1)^n$.
   • Solving, $A = -1$.

Thus, the general solution is: $a_n = C \cdot 2^n - (-1)^n$ Using $a_0 = 2$: $2 = C \cdot 2^0 + 1 \Rightarrow C = 1$ So, the solution is: $a_n = 2^n - (-1)^n$

(c) $a_n = 2a_{n-1} + n$, with $a_0 = 1$

1. Homogeneous Solution: Solve $a_n^{(h)} = 2a_{n-1}^{(h)}$.

   • Assume $a_n^{(h)} = C \cdot 2^n$.

2. Particular Solution: Try a solution of the form $a_n^{(p)} = An + B$.

   • Substitute into the recurrence: $An + B = 2(A(n-1) + B) + n$.
   • Solving, we find $A = -1$ and $B = 2$.

Thus, the general solution is: $a_n = C \cdot 2^n - n + 2$ Using $a_0 = 1$: $1 = C \cdot 2^0 + 2 \Rightarrow C = -1$ So, the solution is: $a_n = -2^n - n + 2$

(d) $a_n = 2a_{n-1} + 2n^2$, with $a_0 = 3$

1. Homogeneous Solution: Solve $a_n^{(h)} = 2a_{n-1}^{(h)}$.

   • Assume $a_n^{(h)} = C \cdot 2^n$.

2. Particular Solution: Try a solution of the form $a_n^{(p)} = An^2 + Bn + C$.

   • Substitute into the recurrence: $An^2 + Bn + C = 2(A(n-1)^2 + B(n-1) + C) + 2n^2$.
   • Solving, we find $A = 2$, $B = 2$, and $C = 1$.

Thus, the general solution is: $a_n = C \cdot 2^n + 2n^2 + 2n + 1$ Using $a_0 = 3$: $3 = C \cdot 2^0 + 1 \Rightarrow C = 2$ So, the solution is: $a_n = 2^{n+1} + 2n^2 + 2n + 1$

Would you like more details on any specific part?

Here are five related questions for further practice:

1. How would you approach finding the homogeneous and particular solutions for second-order recurrence relations?
2. Can you solve a recurrence relation with variable coefficients, such as $a_n = n \cdot a_{n-1}$?
3. What changes if the recurrence relation has a constant term added, like $a_n = 4a_{n-1} + 5$?
4. How do initial conditions influence the particular solution in non-homogeneous recurrence relations?
5. How can we convert recurrence relations into closed-form solutions using generating functions?

Tip: To check your solution, plug the recurrence solution back into the equation to verify it satisfies both the recurrence and the initial condition.