General Solution and Particular Solution of Recurrence Equation

Question

I am given:

$S_{n+2} = S_{n+1}+S_{n} + {2}$ for $\forall n \in N$

My question is how do I find the general solution of the recurrence equation. And the particular solution where $S_0=1$ and $S_1 = 5 $?

Answer 1

First you go from inhomogeneous to homogeneous: $$ S_{n+2} = S_{n+1} + S_n + 2 \\ S_{n+3} = S_{n+2} + S_{n+1} + 2 \\ $$ so $$ S_{n+3} - S_{n+2} = S_{n+2} - S_{n} $$ or $$ S_n = 2 S_{n-1} + 0 \cdot S_{n-2} - S_{n-3} $$ then you solve that one, using the initial conditions. The characteristic polynomial is: $$ p(t) = t^3 - 2 t^2 + 1 $$ We guess the root $r_1 = 1$ and have $$ p(t) = (t - 1)(t^2 - t - 1) $$ so the other two roots are $$ r_{2,3} = \frac{1 \pm \sqrt{5}}{2} $$ where $r_2$ is the golden ratio. This gives $$ S_n = k_1 1^n + k_2 \left( \frac{1 + \sqrt{5}}{2} \right)^n + k_3 \left( \frac{1 - \sqrt{5}}{2} \right)^n $$ We have $$ S_2 = S_1 + S_0 + 2 = 5 + 1 + 2 = 8 $$ We get the linear system $$ \begin{pmatrix} 1 & 1 & 1 \\ 1 & \frac{1 + \sqrt{5}}{2} & \frac{1 - \sqrt{5}}{2} \\ 1 & \left(\frac{1 + \sqrt{5}}{2}\right)^2 & \left(\frac{1 - \sqrt{5}}{2}\right)^2 \end{pmatrix} \begin{pmatrix} k_1 \\ k_2 \\ k_3 \end{pmatrix} = \begin{pmatrix} 1 \\ 5 \\ 8 \end{pmatrix} $$ The numerical solution is $k_1 = -2$, $k_2 = 3.95967$, $k_3 = -0.95967$, so $$ S_n = -2 + 3.95967 \left(\frac{1 + \sqrt{5}}{2}\right)^n -0.95967 \left(\frac{1 - \sqrt{5}}{2}\right)^n $$ Algebraic solution: $$ \left( \begin{array}{rrr|r} 1 & 1 & 1 & 1 \\ 1 & \frac{1 + \sqrt{5}}{2} & \frac{1 - \sqrt{5}}{2} & 5 \\ 1 & \left(\frac{1 + \sqrt{5}}{2}\right)^2 & \left(\frac{1 - \sqrt{5}}{2}\right)^2 & 8 \end{array} \right) \to \\ \left( \begin{array}{rrr|r} 1 & 1 & 1 & 1 \\ 0 & -1 & -1 & -3 \\ 1 & \left(\frac{1 + \sqrt{5}}{2}\right)^2 & \left(\frac{1 - \sqrt{5}}{2}\right)^2 & 8 \end{array} \right) \to \\ \left( \begin{array}{rrr|r} 1 & 0 & 0 & -2 \\ 0 & 1 & 1 & 3 \\ 1 & \left(\frac{1 + \sqrt{5}}{2}\right)^2 & \left(\frac{1 - \sqrt{5}}{2}\right)^2 & 8 \end{array} \right) \to \\ \left( \begin{array}{rrr|r} 1 & 0 & 0 & -2 \\ 0 & 1 & 1 & 3 \\ 0 & \left(\frac{1 + \sqrt{5}}{2}\right)^2 & \left(\frac{1 - \sqrt{5}}{2}\right)^2 & 10 \end{array} \right) \to \\ \left( \begin{array}{rrr|r} 1 & 0 & 0 & -2 \\ 0 & 1 & 1 & 3 \\ 0 & 0 & \left(\frac{1 - \sqrt{5}}{2}\right)^2 - \left(\frac{1 + \sqrt{5}}{2}\right)^2 & 10 - 3 \left(\frac{1 + \sqrt{5}}{2}\right)^2 \end{array} \right) \to \\ \left( \begin{array}{rrr|r} 1 & 0 & 0 & -2 \\ 0 & 1 & 1 & 3 \\ 0 & 0 & \frac{1 - \sqrt{5}}{2} - \frac{1 + \sqrt{5}}{2} & 7 - 3 \frac{1 + \sqrt{5}}{2} \end{array} \right) \to \\ \left( \begin{array}{rrr|r} 1 & 0 & 0 & -2 \\ 0 & 1 & 1 & 3 \\ 0 & 0 & 1 & \left( 3 \frac{1 + \sqrt{5}}{2} - 7 \right)/\sqrt{5} \end{array} \right) \to \\ \left( \begin{array}{rrr|r} 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & \frac{11}{2\sqrt{5}} + \frac{3}{2} \\ 0 & 0 & 1 & -\frac{11}{2\sqrt{5}} + \frac{3}{2} \end{array} \right) $$ So this gives $$ S_n = -2 + \frac{3+11/\sqrt{5}}{2} \left(\frac{1 + \sqrt{5}}{2}\right)^n + \frac{3-11/\sqrt{5}}{2} \left(\frac{1 - \sqrt{5}}{2}\right)^n $$

Answer 2

Just rewrite it as $S_{n+2} + a = S_{n+1} + a + S_{n} + a$
What is $a$? Apparently $a = 2$ in your example.

Now put: $T_n = S_n + 2$.
You get: $T_{n+2} = T_{n+1} + T_{n}$
This is a linear recurrence relation.
From here you can find the characteristic polynomial, and its roots $x_1$
and $x_2$ (in this case these are the golden ratio and its conjugate).

The general solutions is then:
$T_{n} = C_1 . x_1^n + C_2 . x_2^n$
Now you just have to find the constants $C_1$ and $C_2$.
For doing this use what you know about $T_0$ and $T_1$,
build a system and solve it for $C_1$ and $C_2$.

Answer 3

The key point is: consider the sequence $$R_n:=S_n+2$$ then $R_{n+2}=R_{n+1}+R_n$ and you have a Fibonacci-type recurence (the standard Fibonacci is for $R_1=R_2=1$). Apply the standard method of solving linear recurrences (just google for "method of solving linear recurrences")