Find the explicit formula for this recurrence relation

Question

Solve this recurrence relation:

$$a_0 = 1$$ $$a_n = 2^{2(5-n)+1}* a_{n-1} + 1$$

We've only covered linear homogeneous recurrence relation in our course so I'm a little lost and any help would be appreciated.

Answer 1

Here, $a_0 = 1$ and $a_n = 2^{11-2n} a_{n-1} + 1$

First, let us solve a recurrence relation of the form $b_n = b_{n-1} + c_n$ where $c_n$ is explicitly given and $b_0$ is given.

Then, $b_n - b_{n-1} = c_n \implies \sum\limits_{k=1}^n (b_k - b_{k-1}) = \sum\limits_{k=1}^n c_k \implies b_n - b_0 = \sum\limits_{k=1}^n c_k$

So, now the original recurrence relation can actually be transformed into a recurrence realtion just discussed above.

Let $(x_n)$ be a sequence such that $2^{11-2n} x_n = x_{n-1}$, then it can be seen that $a_n x_n = 2^{11-2n}a_{n-1} x_n + x_n = a_{n-1} x_{n-1} + x_n$ , so it is of the form $b_n = b_{n-1} +c_n$ where $b_n = a_n x_n$ and $c_n = x_n$.

Lets solve $2^{11-2n} x_n = x_{n-1}$

$2^{11-2n} x_n = x_{n-1} \implies \dfrac{x_n}{x_{n-1}} = 2^{2n-11} \implies \log_2(x_n) - \log_2(x_{n-1}) = 2n-11$ , again it is of the form $b_n = b_{n-1} +c_n$ where $b_n = \log_2(x_n)$ and $c_n = 2n-11$

$\implies \log_2(x_n) - \log_2(x_0) = \sum\limits_{k=1}^n(2k-11) = n^2-10n$

$\implies x_n = 2^{n^2-10n} x_0$ , now the exact value of $x_0$ doesn't really matters, so let it be $2^{25}$, then $x_n = 2^{(n-5)^2}$

Now, $2^{(n-5)^2}a_n = 2^{((n-1)-5)^2}a_{n-1} + 2^{(n-5)^2} \implies 2^{(n-5)^2}a_n = 2^{(0-5)^2}a_{0} + \sum\limits_{k=1}^n 2^{(k-5)^2}$

Final answer (although not a really nice closed form!) is

$$a_n = \dfrac{2^{25} + \sum\limits_{k=1}^n 2^{(k-5)^2}}{2^{(n-5)^2}}$$