Solve the non-homogenous recurrence $h_n = 3h_{n-1} + 3(2)^n, h_0 = 1$? I am trying to solve the non-homogenous recurrence $h_n = 3h_{n-1} + 3(2)^n, h_0 = 1$.
I can see that the solution to the homogenous $h_n = 3h_{n-1}$ is clearly $h_n = 3^n$. That being said, I have no idea how to solve $h_n - 3h_{n-1} = 3(2)^n$: I assume it's some solution of the sort $(c_1n + c_2)(2)^n$, but I don't know where we'd go from here! Can anyone give advice?
 A: Welcome to MSE!
You could always use generating functions, but that machinery isn't necessary here. Instead, there's a standard trick. Write
$$t_n = \frac{h_n}{2^n}$$
Then after dividing both sides by $2^n$ your recurrence becomes
$$t_n = \frac{3}{2}t_{n-1} + 3$$
Do you see how to solve this recurrence for $t$? Do you see how that will solve your original problem too?

I hope this helps ^_^
A: Let $ n\in\mathbb{N}^{*} $, note that for all $ k\in\mathbb{N} $, we have : \begin{aligned}h_{n-k}&=3h_{n-k-1}+3\times 2^{n-k}\\ \iff \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 3^{k}h_{n-k}&=3^{k+1}h_{n-k-1}+3^{k+1}\times 2^{n-k}\\ \Longrightarrow\sum_{k=0}^{n-1}{\left(3^{k}h_{n-k}-3^{k+1}h_{n-k-1}\right)}&=3\times 2^{n}\sum_{k=0}^{n-1}{\left(\frac{3}{2}\right)^{k}}\\ \iff \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ h_{n}-3^{n}h_{0}&=3\times 2^{n}\times\frac{\left(\frac{3}{2}\right)^{n}-1}{\frac{3}{2}-1}\\ \iff\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  h_{n}&=3^{n}+6\left(3^{n}-2^{n}\right)\end{aligned}
A: Using @HallaSurvivor solution
$$h_n = 3h_{n-1} + 3(2)^n$$
$$h_n=2^n t_n \implies 2t_n=3t_{n-1}+6$$Now, let $t_n=u_n+k$ and replace
$$2u_n+2k=3u_{n-1}+3k+6$$ If you make
$$2k=3k+6\implies k=-6\implies 2u_n=3u_{n-1}$$ Solve for $u_n$ (simple), go back to $t_n=u_n-6$ and to $h=2^n t^n$.
