Solving recurrence relation of this form by iteration for closed form

Question

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.

Answer 1

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

Answer 2

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