Recurrence relation with non-constant coefficients $a_n=1+\frac{1}{2^{n+1}}a_{n+1}+\frac{2^{n+1}-1}{2^{n+1}}a_{n-1}$

Question

Is there a general form to solve a recurrence relation with non-constant coefficients?

Specifically, I'm interested in solving:

$$a_n=1+\frac{1}{2^{n+1}}a_{n+1}+\frac{2^{n+1}-1}{2^{n+1}}a_{n-1}$$ with $a_0=0$.

Thanks!

Answer 1

There is no "general form", and in many cases there is no closed form at all.
In this case, you might look at generating functions.

If $g(x) = \sum_{n=0}^\infty a_n x^n$ is the generating function, by summing your recursion times $x^n$ for $n=1$ to $\infty$, I get

$$ g(x) = \frac{x}{1-x} + \frac{1}{x} \left(g\left(\frac{x}{2}\right) - a_1 \frac{x}{2}\right) + x g(x) - \frac{x}{4} g\left(\frac{x}{2}\right)$$

which "simplifies" to

$$ g(x) = \frac{x^2-4}{4 x (x-1)} g\left(\frac{x}{2}\right) + \frac{(a(1)+2) x - a(1)}{2(x-1)^2} $$

Answer 2

Let $A(x)=\sum_{i=0}^\infty a_nx^n$. Suppose also that we have $a_1$. Keep in mind that the recurrence relation is $a_{n+1} = 2^{n+1}a_n - 2^{n+1} - (2^{n+1}-1)a_{n-1}$.

Then $$ A(x)=\sum_{i=0}^\infty a_nx^n = a_0 + a_1 x + \sum_{i=2}^\infty a_nx^n = a_1x + \sum_{i=0}^\infty a_{n+2}x^{n+2}=\cdots $$ Now we use the above recurrence relation $$ \cdots = a_1 x + \sum_{i=0}^\infty 2^{n+2}a_{n+1}x^{n+2} - \sum_{i=0}^\infty 2^{n+2}x^{n+2} - \sum_{i=0}^\infty (2^{n+2}a_{n}x^{n+2} + \sum_{i=0}^\infty a_{n}x^{n+2} = \cdots $$ $$ \cdots =a_1 x + 2x\sum_{i=0}^\infty a_{n+1}(2x)^{n+1} - 4x^2\sum_{i=0}^\infty(2x)^{n} - 4x^2\sum_{i=0}^\infty a_n(2x)^n + x^2\sum_{i=0}^\infty a_nx^n $$ The first sum is equal to $\sum_{i=0}^\infty a_n(2x)^n$ since $a_0=0$. The second sum is $\frac{1}{1-2x}$. The third one is equal to the first one, and they are both equal to $A(2x)$. The last sum is simply $A(x)$. Plugging it all in, we get:

$$ A(x) = a_1x + 2xA(2x) - \frac{4x^2}{1-2x} - 4x^2 A(2x) + x^2A(x). $$

$$ A(x) (1-x^2) - 2x\cdot A(2x)(1-2x) = a_1x - \frac{4x^2}{1-2x} $$

I'm not really sure where to go from here, but finding a closed form for $A(x)$ will give a closed form for $a_n$'s. It doesn't always have to exist. Maybe one can solve the above equation, or turn it into a differential equation. Anyway I hope this helps.