Solving Recurrence Relation problem I am trying to solve the recurrence relation:
$$G_n = \frac{1-G_{n-1}}{4}$$
$$G_0 = 0$$
$$G_1 = \frac{1}{4}$$
I am told that the answer is
$$G_n = \frac{1}{5}\left(1+\left(\frac{-1}{4}\right)^{n+1}\right)$$
I have found the characteristic equation to be 
$$G_n = B\left(\frac{-1}{4}\right)^{n}$$
But then I am not sure how to continue.
 A: You have $G_n=\frac{1}{4}-\frac{1}{4}G_{n-1}$. With the ansatz $G_n=r^n$ we have for the homogeneous
$$r^n=-\frac{1}{4}r^{n-1}$$
$$r=-\frac{1}{4}$$
and for the particular
$$K=\frac{1}{4}-\frac{1}{4}K$$
$$K=\frac{1}{5}$$
so the general solution is $G_n=\frac{1}{5}+B\left(-\frac{1}{4}\right)^n$ and we plug in the initial conditions to get $0=\frac{1}{5}+B$, so $B=-\frac{1}{5}$.
Thus $G_n=\frac{1}{5}\left( 1-\left(-\frac{1}{4}\right)^n\right)$.
By the way, the answer you were given is not consistent with the initial values. If you plug in $n=0$ you get $G_0=\frac{3}{20}$.
A: $4G_n = 1- G_{n-1}\Rightarrow 4G_n + G_{n-1} = 1 = 4G_{n-1}+G_{n-2}\Rightarrow 4(G_n-G_{n-1}) = - (G_{n-1}-G_{n-2})\Rightarrow G_n -G_{n-1} = -\dfrac{1}{4}\left(G_{n-1}-G_{n-2}\right)= \left(-\dfrac{1}{4}\right)^{n-1}\left(G_1-G_0\right)= (-1)^{n-1}\cdot \left(\dfrac{1}{4}\right)^{n}=-\left(-\dfrac{1}{4}\right)^{n}\Rightarrow G_n = G_0+\displaystyle \sum_{k=1}^n(G_k-G_{k-1})= - \displaystyle \sum_{k=1}^n \left(-\dfrac{1}{4}\right)^{k}=....$. Can you finish it? 
A: By rewriting the recurrence formula we have $G_n=\dfrac{1}{4}-\dfrac{1}{4}G_{n-1}$.
If we write the first elements of the sequence we get:
$$\begin{align*}
G_0&=0,  G_1=\dfrac{1}{4} \\
G_2&=\dfrac{1}{4}-\dfrac{1}{4}G_1 =\dfrac{1}{4}-\left(\dfrac{1}{4}\right)^2\\
G_3&=\dfrac{1}{4}-\dfrac{1}{4}G_2 =\dfrac{1}{4}-\dfrac{1}{4}\left(\dfrac{1}{4}-\left(\dfrac{1}{4}\right)^2\right)\\
& \hspace{2.3cm}=\dfrac{1}{4}-\left(\dfrac{1}{4}\right)^2+\left(\dfrac{1}{4}\right)^3\\
\vdots & \hspace{3cm}\vdots\\
G_n&=^{(?)}\sum_{k=1}^n (-1)^{k+1}\dfrac{1}{4^k}=(-1)\cdot \sum_{k=1}^n \left(\dfrac{-1}{4}\right)^k
\end{align*}$$
Once you have proved the recurrence formula then by properties of geometric series you get
$$G_n=(-1)\cdot \sum_{k=1}^n \left(\dfrac{-1}{4}\right)^k=(-1)\left(\dfrac{1-(-\frac{1}{4})^{n+1}}{1-(-\frac{1}{4})}-1\right)=\dfrac{-1}{1+\frac{1}{4}}\left(1-\left(-\frac{1}{4}\right)^{n+1}-\dfrac{5}{4}\right)=\dfrac{-4}{5}\left(-\dfrac{1}{4}-\left(-\frac{1}{4}\right)^{n+1}\right)=\dfrac{1}{5}\left(1-\left(-\frac{1}{4}\right)^{n}\right)$$
A: The answer via generating functions may be of interest: Let $G(x)=\sum_{n=0}^\infty G_n x^n$. Since the recurrence relation can be written as $4G_n-G_{n-1}=1$ for $n\geq 1$, we have 
\begin{align}
(4+x)G(x)
&=G_0+(4G_1-G_0)x+(4G_2-G_1)x^2+\cdots+(4G_n-G_{n-1})x^n+\cdots \\
&= x+x^2+\cdots = \frac{x}{1-x}.
\end{align}
Solving for $G(x)$ and decomposing into partial fractions yields $$G(x)=\dfrac{x}{(1-x)(4+x)}=\frac15\left(\frac{1}{1-x}-\frac{1}{1+x/4}\right),$$
whereupon we expand these series and match term-by-term to obtain $G_n=\dfrac{1}{5}(1-(-4)^{-n})$.
