How to find a formula of this generating sequence?

Question

It is given that $I_0=0$ and $S_0=0$ $$I_n=I_{n-1}+1$$ $$S_n=3S_{n-1}+5I_n$$ How to come up with a formula for $S_n$?

Answer 1

Hint

Taking into account Daniel Littlewood's comment, you have $$S_n=3S_{n-1}+5 n$$ Let us suppose that $S_n=T_n+\alpha+\beta n$ and replace. So $$T_n+\alpha+\beta n=3\big(T_{n-1}+\alpha+\beta (n-1)\big)+5n$$ Now expand the rhs $$T_n+\alpha+\beta n=3T_{n-1}+3\alpha+3\beta n - 3\beta+5n=3T_{n-1}+3(\alpha-\beta)+(3\beta+5)n$$ So, this gives us two equations $$\alpha=3(\alpha-\beta)$$ $$\beta=3\beta+5$$

I am sure that you can take from here.

Answer 2

$$S(x) = 3x*S(x) + 5*x/(1 -x)^2$$ So $$S(x) = 5x/((1-3x)(1-x)^2$$ Use partial fraction decomposition to get $$-(5/(2 (-1 + x)^2)) + 5/(4 (-1 + x)) - 15/(4 (-1 + 3 x))$$ So $$s_n = 5/4 (-3 + 3^(1 + n) - 2 n)$$