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

In summary, the conversation is about deriving an exact formula for the recursive sequence $s_n = 2_{s_n-1} - s_{n-2}$ where $n \ge 2$, and $s_0 = 4$, $s_1 = 1$. The solution involves finding the characteristic root, which is $r=1$, and using initial conditions to determine the values of the parameters. The closed-form for the sequence is $s_n=c_1+c_2n$.
  • #1
shamieh
539
0
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.
 
Physics news on Phys.org
  • #2
For my solution I ended up with $S_n = 4*1^n - 3n1^n$
 
  • #3
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?
 
Back
Top