0

Solve the recurrence relation where $S_n=3S_{n-1}+3;S_0=10$

I tried using the iterative method but I am completely lost. Any help is much appreciated.

nova_star
  • 463
  • Replace $S_n=a\times 3^n+b$ in the recurrence relation and try to find $a$ and $b$, noting that $S_0=10$ – Qurultay Mar 16 '18 at 20:00
  • Alt. hint: look for a $,k,$ such that the relation can be written as $S_n+k=3\left(S_{n-1}+k\right)$. Comparing with the original, it follows that $,2k=3,$, then $,S_n+\frac{3}{2}=3\left(S_{n-1}+\frac{3}{2}\right),$ means that $,S_n+\frac{3}{2},$ is a GP. – dxiv Mar 16 '18 at 20:08
  • What does "solve" mean here? –  Mar 17 '18 at 06:30
  • I thought it meant to write in the recurrence relation in a simplified form, in terms of n, so that we can easily compute the nth term without having to calculate the ( n-1)th term – nova_star Mar 17 '18 at 14:42

4 Answers4

2

First, look for $a $ such that $(S_n+a)$ is geometric.

Put $u_n=S_n+\frac {3}{2} $.

then

$$u_n=3u_{n-1}$$ and

$$u_n=3^nu_0$$ with $$u_0=S_0+\frac {3}{2}=\frac {23}{2} $$ finally

$$S_n=\frac {23}{2}3^n-\frac {3}{2} .$$

hamam_Abdallah
  • 62,951
2

Note that $$\begin{align}S_n&=3S_{n-1}+3\\&=3^2S_{n-2}+3^2+3\\&=3^3S_{n-3}+3^3+3^2+3\\&=\cdots\\&=3^nS_{n-n}+\sum_{k=1}^n 3^k\\&=10(3^n)+\frac{3^{n+1}-3}2\end{align}$$ so $$\boxed{S_n=\frac{23}2\cdot3^n-\frac32}$$

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 27,005
1

solve the homogeneous equation $$s_n=3s_{n-1}$$ with $$s_n=q^n$$ we get $$s_n=C3^{n-1}$$ now you will Need a special solution of the inhomogeneous equation and using the equation $$s_0=10$$ we get $$s_n=\frac{1}{2}(23\cdot 3^n-3)$$

Dr. Sonnhard Graubner
  • 95,283
1

Consider the formal power series $f(z) = \sum_{n=0}^\infty S_n z^n$. Multiplying both sides of the recurrence relation by $z^n$ and summing over $n$, we have $$ \sum_{n=1}^\infty S_nz^n = \sum_{n=1}^\infty 3S_{n-1}z^n + 3\sum_{n=1}^\infty z^n. $$ Writing this in terms of $f(z)$ we have $$ f(z) - 10 = 3zf(z) + \frac{3z}{1-z}, $$ and solving for $f(z)$ yields $$ f(z) = \frac{10}{1-3z} + \frac{3z}{(1-z)(1-3z} = \frac{10-7z}{(1-z)(1-3z)}. $$ Partial fraction decomposition yields $$ f(z) = \frac{23}2 \left(\frac1{1-3z}\right) -\frac32\left(\frac1{1-z}\right) , $$ and hence $$ f(z) = \sum_{n=0}^\infty \left(\frac{23}2\cdot 23^n - \frac32 \right)z^n. $$ It follows that $$ S_n = \left(\frac{23}2\right)^n - \frac32. $$

Math1000
  • 36,983