I haven't take any discrete mathematics course but I know quite basics of it but when there is a recurrence in which the gap is $2$ or more, I get in trouble. I know for the above mentioned examples taking few terms will help but I want to know the following:
How to find explicit formula for recurrences of the form $$y_{n}=a(n)y_{n-2}$$ using this only :$$y_n=f_0\prod_{i=1}^{n}a(i)+\sum_{k=0}^{n-1} b(n-k)\prod_{j=1}^{k}a(n-j+1)$$ which solves for $$y_{n}=a(n)y_{n-1}+b(n)$$
Your summation factor is going to be $\frac{4^n}{n!(n-1)!}$. So let $$ y_n = \frac{4^n}{n!(n-1)!}x_n \\ \frac{4^n}{n!(n-1)!}x_n = \frac{4}{(n)(n-1)}\frac{4^{n-1}}{(n-1)!(n-2)!}x_{n-1} =\frac{4^n}{n!(n-1)!}x_n \\ $$ Thus $$x_n = x_{n-1} $$ and $$y_n = k \frac{4^n}{n!(n-1)!} $$ for some constant $k$. If you were given some value for $y_1$ then this would read $$ y_n = \frac{4^{n-1}}{n!(n-1)!}y_1 $$