# variable degree recurrence relation

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 !

• In your 2nd question, $a_1$ seems to be undefined, because the final term in the sum would be $a_{n-\left \lfloor \frac{n}{2} \right \rfloor} = a_1$ which is itself. – browngreen Mar 21 '17 at 2:08
• yes, thanks! $a_1$ is needed there. Actually, I randomly took any simple $f(n) \leq n$ just to make the degree variable. You can safely assume any terminating condition. – Debashish Mar 21 '17 at 2:14