Solve for $a_{n}$ where $a_{n} = 4a_{n-1} + 2^{2n-1}$, $a_0=1$ and $a_1=6$ .

Question

$a_{n} = 4a_{n-1} + 2^{2n-1}$, $a_0=1$ and $a_1=6$.

So I am trying to find $a_n$ by using the generating function let's call it $A(x)$. the equation then is written as (if I doing this correctly) : $A(x)-ao = 4xA(x) + \sum_{k=1}2^{2n-1}*x^k$ now for $\sum_{k=0}2^{2n-1}*x^k = \sum_{k=1}\frac{1}{2}4^{k}x^k \mapsto \frac{1}{2}\frac{1}{1-4x} - \frac{1}{2}$ Then we have: $(1-4x)A(x)= 1+\frac{1}{2}\frac{1}{1-4x} -\frac{1}{2}\Rightarrow A(x)=\frac{1}{2}\frac{1}{1-4x}+\frac{1}{2}\frac{1}{(1-4x)^2}\\ \Rightarrow a_n= ? $ $ (1-4x)^{-2} \mapsto 1 + \sum_{k=1}\binom{2+k-1}{k}*4^kx^{k}\\ \Rightarrow \frac{1}{(1-4x)^2}= 1+ \sum_{k=1}\binom{1+k}{k}*4^kx^{k} = 1+ \sum_{k=1}(k+1)4^kx^{k}= \sum_{k=0}(k+1)4^kx^{k}$ $And, \frac{1}{1-4x} \mapsto 4^n$ So $an = \frac{1}{2}4^n + \frac{1}{2}(n+1)4^n$ agrees with a1 = 6

Answer 1

Your initial equation for $A(x)$ is incorrect. You need to work the boundary condition $a_0 = 1$ into the equation. (The condition $a_1=6$ is redundant, since it can be computed from $a_0$ and the recurrence relation.)

There is more than one way to do this, but one way is to write the recurrence equation so it is true for all $n$. Although you did not state the restriction, the equation $a_n = 4 a_{n-1}+2^{2n-1}$ only holds for $n \ge 1$. It is important to state such restrictions explicitly in order to avoid errors.

So here is how to revise the equation so it holds for all $n$. Notice that if we simply let $n=0$ in the original equation, we have $1 = 0 + 2^{-1}$, which is obviously false. (We adopt the convention that $a_n = 0$ for all $n < 0$.) To patch things up, we write $$a_n = 4 a_{n-1}+2^{2n-1} + (1/2) \delta_{0n}$$ where $\delta$ is the Kronecker delta function. Now we have a relation that is true for all $n$, so $$a_n x^n = 4 a_{n-1} x^n +2^{2n-1} x^n + (1/2) \delta_{0n} x^n$$ for all $n$. Summing over $n=0,1,2,\dots$, we have $$\sum_{n=0}^{\infty} a_n x^n = 4 \sum_{n=0}^{\infty} a_{n-1} x^n + \sum_{n=0}^{\infty}2^{2n-1} x^n + 1/2 $$ so $$A(x) = 4x A(x) + \frac{1}{2} \cdot \frac{1}{1-4x} + \frac{1}{2}$$ Maybe you can take it from here.

Answer 2

Note, you didn't provide the boundary value for $a_1$.

Do you specifically want to use a GF? If you set $$ b_n = \frac{a_n}{2^{2n-1}} $$ to get (since $2(n-1)-1 = 2n -3$) $$ b_n = b_{n-1} + 1 $$ and, $$ a_n = 2^{n-2}a_1 + 2^{n-1} $$