2
$\begingroup$

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?

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

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

$\endgroup$
1
$\begingroup$

$$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\,$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.