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

AI Thread Summary
The discussion focuses on solving the recurrence relation $s_n = 2s_{n-1} - s_{n-2}$ with initial conditions $s_0 = 4$ and $s_1 = 1$. Participants explore the characteristic equation, identifying a double root at $r = 1$, leading to a general solution of the form $s_n = C_1 + C_2 n$. To find the constants $C_1$ and $C_2$, they apply the initial conditions, resulting in a system of equations. Solving this system yields the closed-form expression for the sequence. The final closed-form solution is derived from these parameters.
shamieh
Messages
538
Reaction score
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
For my solution I ended up with $S_n = 4*1^n - 3n1^n$
 
You have correctly identified that the characteristic root is $r=1$ of multiplicity 2, thus the closed-form is:

$$s_n=c_1+c_2n$$

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

$$s_0=c_1+c_2\cdot0=4$$

$$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