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 !

  • $\begingroup$ 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. $\endgroup$ – browngreen Mar 21 '17 at 2:08
  • $\begingroup$ 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. $\endgroup$ – Debashish Mar 21 '17 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.