(Solved): 12. a. Consider the following recursion relation \[ \begin{aligned} T(0) &=0 \\ T(1) &=1 \\ T(n+1) ...
12. a. Consider the following recursion relation \[ \begin{aligned} T(0) &=0 \\ T(1) &=1 \\ T(n+1) &=T(n)+2 T(n-1) \end{aligned} \] for all \( n \geq 1 \). Prove, by induction on the input \( n \), that \[ T(n)=\frac{2^{n}-(-1)^{n}}{3} \] for all \( n \geq 0 \). You should clearly state your induction hypothesis, base case(s) and induction step. \( [10 \) marks] b. Consider the following set of propositional clauses (numbered for reference): \[ \begin{array}{l} (\neg P \vee R) \\ (\neg P \vee Q \vee T) \\ (Q \vee \neg R \vee \neg T) \\ (P \vee R \vee S) \\ (P \vee \neg R) \\ (P \vee R \vee \neg S) \\ (\neg P \vee \neg Q) \end{array} \] Use the Davis-Putnam-Logemann-Loveland (DPLL) algorithm to determine whether the above set of clauses is satisfiable. You should state which rule is being applied in each instance. [10 marks]
c. Prove that SAT is polynomially reducible to 3 SAT by describing a polynomialtime algorithm for converting an instance of SAT into an instance of 3SAT. You should explain why your algorithm terminates. [5 marks]