Solving recurrence relations of type $S_n-7S_{n-1}+10S_{n-2}=5\cdot 3^n$

Question

I know how to solve this kind of equasions $$S_n-7S_{n-1}+10S_{n-2}=5\cdot 3^n$$ $$S_0=0, S_1=1$$ for example...but when there is a constant (example:$(3^n+5))$ or $(5\cdot 3^n)$ i don't know how to solve it. Any tips.

Answer 1

Since the characteristic polynomial is $z^2-7z+10 = (z-2)(z-5)$, the solutions of $$ S_{n}-7 S_{n-1} + 10 S_{n-2} = 0 $$ have the form $S_n = \alpha 2^n+\beta 5^n$. By direct inspection a solution of $$ S_{n}-7 S_{n-1} + 10 S_{n-2} = 5\cdot 3^n $$ is given by $S_n=-\frac{45}{2}\cdot3^n$, hence the set of solutions of the previous recurrence is given by $$ S_n = \alpha 2^n+\beta 5^n-\frac{45}{2}3^n $$ and by imposing $S_0=0$ and $S_1=1$ we get: $$\boxed{ S_n = \color{red}{\frac{44}{3}2^n + \frac{47}{6} 5^n -\frac{45}{2} 3^n}.} $$

Answer 2

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &S_{n} - 7S_{n - 1} + 10S_{n - 2} = 5 \times 3^n\implies 3^{-n}S_{n} - {7 \over 3}\bracks{3^{-\pars{n - 1}}S_{n - 1}} + {10 \over 9}\bracks{3^{-\pars{n - 2}}S_{n - 2}} = 5 \\[5mm] & \implies \bracks{3^{-n}S_{n} + {45 \over 2}} - {7 \over 3}\bracks{3^{-\pars{n - 1}}S_{n - 1} + {45 \over 2}} + {10 \over 9}\bracks{3^{-\pars{n - 2}}S_{n - 2} + {45 \over 2}} = 0 \end{align}

The characteristic equation for $\ds{3^{-n}S_{n} + {45 \over 2}}$ has the roots $\ds{2/3}$ and $\ds{5/3}$:

\begin{align} &3^{-n}S_{n} + {45 \over 2} = a\pars{2 \over 3}^{n} + b\pars{5 \over 3}^{n} \implies \left\{\begin{array}{rcl} \ds{45 \over 2} & \ds{=} & \pars{a + b} \\[2mm] \ds{{1 \over 3} + {45 \over 2}} & \ds{=} & \ds{{2 \over 3}\,a + {5 \over 3}\,b} \end{array}\right. \\[5mm] &\ \implies\qquad \left.\begin{array}{rcrcl} \ds{2a} & \ds{+} & \ds{2b} & \ds{=} & \ds{45} \\ \ds{4a} & \ds{+} & \ds{10b} & \ds{=} & \ds{137} \end{array}\right\}\quad\implies\quad \pars{~a = {44 \over 3}\ \mbox{and}\ b = {47 \over 6}~} \\[5mm] &\ \implies 3^{-n}S_{n} + {45 \over 2} = {44 \over 3}\,\pars{2 \over 3}^{n} + {47 \over 6}\,\pars{5 \over 3}^{n} \\[5mm] &\ \implies S_{n} + {45 \over 2}\,3^{n} = {44 \over 3}\,2^{n} + {47 \over 6}\,5^{n}\implies \bbx{S_{n} = {44 \over 3}\,2^{n} - {45 \over 2}\,3^{n} + {47 \over 6}\,5^{n}} \\ & \end{align}

Answer 3

The recurrence can be thought of as a difference equation (discrete analog of a differential equation). Since the difference operator is linear the $z$-transform is a particularly useful tool. Applying the transform we have

$$Z[S_n -7S_{n-1}+10S_{n-2}] = 5\cdot Z[3^n]$$

The RHS is $$ Z[3^n] = \sum_{n = 0}^\infty\left(\frac{3}{z}\right)^n = \frac{1}{1-3z^{-1}}. $$ Furthermore $$ Z[S_{n-k}] = z^{-k}S(z). $$ You can solve for $S(z)$ and invert it to get $S_n$.

Answer 4

Here is how to reduce it into the form you know how to solve: \begin{align} &S_{n+1}-7S_n+10S_{n-1}=5\cdot3^{n+1}\\ \implies &S_{n+1}-7S_n+10S_{n-1}=3(S_n-7S_{n-1}+10S_{n-2})\\ \implies &S_{n+1}-10S_n+31S_{n-1}-30S_{n-2}=0 \end{align} So by solving the recursive polynomial, the solution is of the form $S_n=a2^n+b3^n+c5^n$. Satisfy $S_0,S_1$ and the original equation to get the required answer as $$\boxed{ S_n = \frac{44}{3}2^n-\frac{45}{2} 3^n+ \frac{47}{6} 5^n}$$