Suppose that the sequence of numbers $a_n$ is given by the recurrence $a_n = $ $4a_n$$_−$$_1$ + n with initial value $a_1 = 0$. Prove that $a_n = Θ(4^n)$.
I know I'm supposed to prove $O(4^n)$ and $\Omega(4^n)$ but I'm not exactly sure how to do that
On
Every linear difference equation is like a differential equation, so basically a solution is the sum of a general solution plus a particular solution, whether the initial conditions are fixed the solution is unique. As general solution just solve
$a_n - 4 a_{n-1} = 0$ which it is easy to see that $\gamma_n = c 4^n$ is the general solution, the particular solution is going to be a polynomial $p(n)$, since the known term is a polynomial too. So it is safe to say that
$$a_n = c 4^n + p(n),$$
observe now that the sequence $a_n$ is both positive and strictly increasing (just use the induction on the recursion which defines it), so basically $$a_n \geq c 4^n$$ which assure you that $$a_n \in \Omega(4^n).$$
For the upper bound just observe that for each polynomial and for $n$ big enough $p(n) \leq 4^n \Rightarrow p(n) \in O(4^n)$ so
$$a_n = c4^n + p(n) \in O(4^n).$$
Which completes the proof since $a_n \in O(4^n)$ and $a_n \in \Omega(4^n)$ This is a reasoning without solve the equation, i hope i'm not missing anything, otherwise you can solve the difference equation, find the solution explicitly and reason on such solution.
Actually, we can find an explicit formula for $a_n$, let $b_n=a_n-\frac{1}{3}n-\frac{4}{9}$, then $b_n=4*b_{n-1}$ and $b_1=-\frac{7}{9}$. Therefore $a_n=(-\frac{7}{9})*4^{n-1}+\frac{1}{3}n+\frac{4}{9}$.