Find solutions to each of the following recurrences using the techniques outlined in the lecture notes (“without guessing”). Demonstrate that your closed form finds the same values for several small numbers, and prove by induction that your closed form satisfies the recurrence in general. 1. f(0) = 3 f(n) = 5f(n−1) 2. f(0) = 5 f(n) = f(n−1) + 4 3. f(0) = 2 f(n) = 4f(n−1) + 6 4. f(0) = 3 f(n) = 5f(n−1) + n
