Solving Recurrence Relation problem

Question

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.

Answer 1

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}$.

Answer 2

$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?

Answer 3

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)$$

Answer 4

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})$.