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

Such recurrences are called full history. One way to tackle them is to consider $a_{n + 1} - a_n$, most of the sum falls away and you get something manageable.

Another (more general) way is to use generating functions. Say you have:

$\begin{align*} a_{n + 1} &= \sum_{0 \le k \le n} a_k \end{align*}$

define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply your recurrence by $z^n$ and sum over $n \ge 0$, recognize resulting sums:

$\begin{align*} \sum_{n \ge 0} a_{n + 1} z^n &= \sum_{n \ge 0} z^n \sum_{0 \le k \le n} a_k \\ \frac{A(z) - a_0}{z} &= \frac{A(z)}{1 - z} \end{align*}$

Solve for $A(z)$:

$\begin{align*} A(z) &= \frac{a_0}{2} + \frac{a_0}{2 (1 - 2 z)} \\ a_n &= [z^n] A(z) \\ &= \frac{a_0}{2} [n = 0] + \frac{a_0}{2} \cdot 2^n \end{align*}$

where $[z^n]$ is the "coefficient of $z^n$" operator, and $[n = 0]$ uses Iverson's convention: the bracket is 1 if the condition is true, 0 otherwise.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.