Problem 1
\(a_{n}=2 a_{n-1}+3 a_{n-2}\) for \(n \geq 2\) where \(a_{0}=2\) and \(a_{1}=2\).
Problem 1
Show that the recurrence relation \(a_{n}=a_{n-1} /\left(1+a_{n-1}\right)\) with \(a_{0}=C\) has the function \(S(n)=C /(1+C n)\) as a solution.
Problem 1
Solve \(T(n)=T(n-1)+n\) for \(n \geq 1\) with \(T(0)=2\).
Problem 2
Find solutions for the following recurrences using back substitution, and then verify the correctness of these solutions by induction on \(k\) where \(n=d^{k}\). (a) \(a_{n}=\left\\{\begin{array}{ll}a_{n / d}+e & \text { for } k>0, n=d^{k}, d \neq 1 \\ e & \text { for } n=1\end{array}\right.\) (b) \(\quad a_{n}=\left\\{\begin{array}{ll}\mathrm{Ca}_{n / d}+e & \text { for } C \neq d, C \neq 1, k>0, n=d^{k} \\ e & \text { for } n=1\end{array}\right.\)
Problem 2
\(a_{n}=4 a_{n-1}+21 a_{n-2}\) for \(n \geq 2\) where \(a_{0}=3\) and \(a_{1}=7\).
Problem 2
Solve \(T(n)=T(n-1)+n\) for \(n \geq 1\) with \(T(0)=7\).
Problem 3
Solve \(T(n)=T(n-1)+2 n+1\) for \(n \geq 1\) with \(T(0)=1\).
Problem 3
\(a_{n}+8 a_{n-1}+12 a_{n-2}=0\) for \(n \geq 2\) where \(a_{0}=-2\) and \(a_{1}=6\).
Problem 3
Solve these recurrences using back substitution. Verify the solutions are correct by induction. (a) \(\quad a_{n}=\left\\{\begin{array}{ll}3 a_{n / 2}+4 & \text { for } k>0, n=2^{k} \\ 7 & \text { for } n=1\end{array}\right.\) (b) \(a_{n}=\left\\{\begin{array}{ll}5 a_{n / 5}+7 & \text { for } k>0, n=5^{k} \\\ 12 & \text { for } n=1\end{array}\right.\) (c) \(a_{n}=\left\\{\begin{array}{ll}2 a_{n / 3}+5 & \text { for } k>0, n=3^{k} \\\ 7 & \text { for } n=1\end{array}\right.\) (d) \(a_{n}=\left\\{\begin{array}{ll}7 a_{n / 4}+3 & \text { for } k>0, n=4^{k} \\\ 1 & \text { for } n=1\end{array}\right.\)
Problem 4
Solve \(T(n)=T(n-1)+5\) for \(n \geq 1\) with \(T(0)=1\).
