Solving recurrence relation of this form by iteration for closed form The recurrence relation is of the form:
$$ G(n) = 5G(n-1) +\frac{4^n}{4^2},\quad G(1)=3$$
My answer always differs from that on wolfram Alpha where is my mistake??
My steps are
$ G(n) = 5^2G(n-2) +\frac{5\cdot 4^n}{4^3}+\frac{4^n}{4^2} $
$G(n)= 5^3G(n-3) +\frac{5^2\cdot 4^n}{4^4}+\frac{5\cdot 4^n}{4^3}+\frac{4^n}{4^2} $
and so on after $n-1$ steps of the process we reach $G(1)$ and
$G(n)= \frac{5^n}{5}G(1) +4^n(\frac{5^n}{5^2\cdot 4^n\cdot 4}+\dots+\frac{5}{4^3}+\frac{1}{4^2}) $
then I use the sum of geometric series and sub 3 for $G(1)$. I think the mistake is some where in the above.
 A: Following your approach we have:
$$
\begin{align*}
G(n) &= 5G(n-1) +4^{n-2}=5\left(5G(n-2) +4^{n-3}\right)+4^{n-2}\\&=
5^2G(n-2) +5\cdot 4^{n-3}+4^{n-2}\\
&=5^{n-1}G(1) +5^{n-2}\cdot 4^{0}+\dots+5^1\cdot 4^{n-3}+5^0\cdot4^{n-2}\\
&=5^{n-1}G(1)+5^{n-1}-4^{n-1}=4\cdot 5^{n-1}-4^{n-1}\end{align*},$$
where at the end we used the fact that
$$\frac{x^{n-1}-y^{n-1}}{x-y}=x^{n-2}\cdot y^{0}+\dots+x^1\cdot y^{n-3}+x^0\cdot y^{n-2}.$$
A: You have extra $4$ here: $+4^n(\frac{5^n}{5^2\cdot 4^n\cdot \color{red}{4}}+$.
Preserving the degrees of $4$:
$$\begin{align}G(n) = &5G(n-1) +\frac{4^n}{4^2}=5\left(5G(n-2) +\frac{4^{n-1}}{4^2}\right)+\frac{4^n}{4^2}=\\&5^2G(n-2) +\frac{5\cdot 4^{n-1}}{4^2}+\frac{4^n}{4^2}=5^2\left(5G(n-3) +\frac{4^{n-2}}{4^2}\right)+\frac{5\cdot 4^{n-1}}{4^2}+\frac{4^n}{4^2}=\\
&5^3G(n-3) +\frac{5^2\cdot 4^{n-2}}{4^2}+\frac{5\cdot 4^{n-1}}{4^2}+\frac{4^n}{4^2}=\cdots \\
&5^{n-1}G(1)+\frac{5^{n-2}\cdot 4^2}{4^2}+\frac{5^{n-3}\cdot 4^3}{4^2}+\cdots +\frac{5\cdot 4^{n-1}}{4^2}+\frac{4^n}{4^2}=\\
&3\cdot 5^{n-1}+\frac{5^{n-2}\cdot 4^2}{4^2}\left(1+\frac{4}{5}+\left(\frac45\right)^2+\cdots +\left(\frac45\right)^{n-2}\right)=\\
&3\cdot 5^{n-1}+5^{n-2}\cdot \frac{1\cdot \left(1-\left(\frac45\right)^{n-1}\right)}{1-\frac45}=\\
&3\cdot 5^{n-1}+5^{n-1}-4^{n-1}=\\
&4\cdot 5^{n-1}+4^{n-1}.\end{align}$$
