Solve Recurrence: $s_n = 2_{s_n-1} - s_{n-2}$ | Discrete Math

[shamieh]

Derive an exact formula (solve the recurrence definition) for the following recursive sequence: $s_n = 2_{s_n-1} - s_{n-2}$ where $n \ge 2$, and $s_0 = 4$, $s_1 = 1$.

So I saw someone solving this by making it a differential equation or something?

How would you do that? should I do
let $\alpha = C_1$ let $\beta = C_2$ (because those symbols are ugly)

$r^2 - 2r + 1$ to get:

$r = 1$, $r = 1$

= $C_11^n + C_2n1^n$ ?
But how do I find my $C_1$ and $C_2$ ?

By the way this is a Discrete Mathematics course, not Calculus 4 course.

 

[shamieh]

For my solution I ended up with $S_n = 4*1^n - 3n1^n$

 

[MarkFL]

You have correctly identified that the characteristic root is $r=1$ of multiplicity 2, thus the closed-form is:

\(\displaystyle s_n=c_1+c_2n\)

Now, to determine the values of the parameters, you can use the initial conditions:

\(\displaystyle s_0=c_1+c_2\cdot0=4\)

\(\displaystyle s_2=c_1+c_2\cdot1=1\)

So, what do you get for the parameters when you solve the above system, and hence, what is the closed-form?