All Questions
Tagged with characteristic-polynomial recurrence-relations
12 questions
3
votes
3
answers
114
views
Solving $c_{n} - 2c_{n-1} - 5c_{n-2} - c_{n-3}=0$
Solve the following homogeneous recurrence relation \begin{equation} c_{n} - 2c_{n-1} - 5c_{n-2} - c_{n-3} = 0 \quad\quad n \geq 3 \end{equation} with initial conditions $c_{0} = 0, c_{1} = 1$ and $c_{...
- 1,005
-1
votes
1
answer
101
views
Let $a$ be a sequence where $a_0 = 21$, $a_1 = 35$, and $a_{n+2} = 4a_{n+1} − 4a_n + n^2$ for $n ≥ 2$. Compute $a_{2006} \pmod {100}$
Problem
Let $a_0, a_1, a_2, ...$ be a sequence of real numbers defined
by $a_0 = 21, a_1 = 35$, and $a_{n+2} = 4a_{n+1}-4a_n+n^2$ for $n ≥ 2$. Compute the remainder obtained when $a_{2006}$ is ...
- 119
1
vote
1
answer
77
views
How do you get the characteristic polynomial of a recursion?
For example, the characteristic polynomial of the Fibonacci sequence is $x^2 -x -1$. What are the steps involved in this?
- 11
0
votes
1
answer
176
views
Characteristic polynomial of linear recurrences
I am learning about solving linear recurrences and I am trying to understand the proof behind the solution.
For example, if I have $(a_n)_{n\ge1} \subseteq \mathbb{R}$,
$a_n = c_1a_{n-1} + c_2a_{n-2}+\...
- 1,206
1
vote
2
answers
137
views
solve recurrence relation $a_{n+2}=(a_{n+1}+1)/a_n$
Let $a_1$ = 2015, $a_2$=2016. Find $a_{2017}$, given $a_{n+2}=(a_{n+1}+1)/a_n$
I have found the 2 roots of the characteristic equation $x^2-x-1=0$ :
$r_1 = ((1+\sqrt{5})/2)^n$ , $r_2 = ((1-\sqrt{5})/2)...
- 502
1
vote
1
answer
78
views
What is the characteristic equation of $a_{n+2}+2a_{n}=0$?
So if we let $a_{n}=Cr^n$ then we have $Cr^{n+2}+2Cr^n=Cr^n(r^2+2)$. So I got that the characteristic equation $r^2+2=0$ but it should be $r^2+2r=0$ apparently. How is that?
- 867
7
votes
0
answers
137
views
How to prove that all the roots $x_0$ of $p_n(x) = \frac{x}{f(n)} \sum\limits_{k=1}^n a_k p_{n-k}(x)$ satisfy $- \frac{4d}{a_1^2} f(n) < x_0 \leq 0$?
This question is an extension of Why are the roots of this recursive defined polynomial bound by the roots of the discriminant of the characteristic polynomial?
As I discovered numerically, I can ...
- 399
0
votes
0
answers
77
views
Characteristic polynomial of recursion with exponential term
I have this recurrence relation as part of a larger problem: $a_k=2a_{k-1}+2^{k-2}.$ With recurrence relations with a constant term we can rearrange things and shift the index, but I'm not sure how to ...
3
votes
0
answers
141
views
Using characteristic polynomial for getting an asymptotic information to a recurrence relation with non-constant coefficient
Let's define the following two recurrence relations with $c_{1,2} \in \mathbb{N}$ and $x \in \mathbb{R}$. The constant coefficients $c_1$ and $c_2$ are the same for both recurrence relations.
First ...
- 399
0
votes
1
answer
87
views
Why is $a_n(x) \neq 0$ for $a_n(x) = c_1 x a_{n-1}(x) + c_2 x a_{n-2}(x)$ if the discriminant of the characteristic polynomial $\Delta_{\lambda} > 0$?
Lets define the sequence
$a_0 = 1$, $a_1 = c_1x$ and $a_n = c_1 x a_{n-1} + c_2 x a_{n-2}$ with $c_{1,2} \in \mathbb{N}$ and $x \in \mathbb{R}$.
Then the characteristic polynomial is:
$\lambda^2 - ...
- 399
1
vote
1
answer
1k
views
Fibonacci closed form via vector space of infinite sequences of real numbers and geometric sequences
This question is from Linear Algebra with Applications (5th edition) by Otto Bretscher. It is in section 4.1 (Introduction to vector spaces), question 60. Below is the question:
Consider the ...
- 1,771
2
votes
1
answer
250
views
Solving for the closed form of recurrence relations using characteristic polynomial
I know how to find the closed form of some recurrence relations such as
those that are similar to the Fibonacci Sequence. I am not sure how to solve a recurrence relation using the characteristic ...
- 2,516