How to solve the following types of recurrence relation,
$1$. $\;\;a_n = a_{n-1} + a_{n-1} + a_{n-2} ... + a_{n-n}\;\;\;$ where $\;\;\;a_0 = 1$.
$2$.$\;\;a_n = a_{n-1} + a_{n-1} + a_{n-2} ... + a_{n-\left \lfloor \frac{n}{2} \right \rfloor} \;\;\;$ where $\;\;\;a_0 = 1$.
Using small number I can find that, for first question $a_n = 2^{n-1}$ But, in general,
how to apply root method (assuming $a_n = r^n$) here ? Or please mention other methods like generating function that we use to solve recurrence like $\;\;a_n = A.a_{n-1} + B.a_{n-2}$ (degree $2$ in this case)
Thanks !