# 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. 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. 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.