# Recurrence equation solution: what are the missing steps?

Given $$y(0)=1$$ $$y(n)=3y(n-1)+3^n$$ My attempt so far using reverse substitution method: $$y(n)=3y(n-1)+3^n$$ $$=3^2y(n-2)+3^13^{n-1}+3^n$$ $$=3^3y(n-3)+3^23^{n-2}+3^13^{n-1}+3^n$$ $$=3^iy(n-i)+3^{i-1}3^{n-(i-1)}+\dots+3^23^{n-2}+3^13^{n-1}+3^03^n$$ And this is where I get stuck, I think that the next step should be something like $$3^ny(0)+3^{n-1}3^{NotSureWhatGoesHere}+\dots$$ Using wolframalpha, I get the answer $$y(n)=3^{n-1}(c_1+3n)$$ I feel like I'm quite close, which step am I missing? Is something wrong in what I've done so far?

• What's missing here is an induction argument. – Alexander Burstein Dec 11 '17 at 3:27

Set $i=n$ in the second-to-last equation of yours. Then you get $$y(n)=3^ny(0)+3^{n-1}3^{n-(n-1)}+\dots+3^23^{n-2}+3^13^{n-1}+3^03^n$$ $$=3^ny(0)+n3^n=3^n+n3^n=3^n(1+n)$$ This is consistent with Wolfram Alpha's solution: $c_1=3$.
$$y(n) = \dots = 3^3 * y(n-3) + 3^2*3^{n-2} + 3^1*3^{n-1} + 3^0 * 3^n$$
More simply: $\;y_n = 3^3 \, y_{n-3} + 3 \cdot 3^n\,$.
$$= 3^i * y(n-i) + 3^{i-1} * 3^{n-i-1} + ... + 3^2*3^{n-2} + 3^1 * 3^{n-1} + 3^0* 3^n$$
Then: $\;y_n = 3^i \, y_{n-i} + i \cdot 3^n = \dots = 3^n\,y_0 + n \cdot 3^n\,$.
Or, you could first divide the recurrence by $3^n$ and note that $\displaystyle \frac{y_n}{3^n}$ is an arithmetic progression: $$\displaystyle \frac{y_{n}}{3^n} = \frac{y_{n-1}}{3^{n-1}}+1\,$$