10
votes
4answers
329 views

Converting recursive equations into matrices

How do we convert recursive equations into matrix forms? For instance, consider this recursive equation(Fibonacci Series): $$F_n = F_{n-1} + F_{n-2}$$ And it comes out to be that the following that ...
2
votes
2answers
93 views

Determinant involving recurrence

Evaluate $$\left| A \right| = \left| {\matrix{ {x + y} & {xy} & 0 & \cdots & \cdots & 0 \cr 1 & {x + y} & {xy} & \cdots & \cdots & 0 \cr 0 ...
1
vote
1answer
30 views

How to convert linear recurrence to a tiling question

If I have some linear recurrence of form $$f(n) = a_1f(n-1) + a_2f(n-2) + a_3f(n-3) + \cdots + a_kf(n-k)$$ How does this translate to tilings? For example the Fibonacci sequence is the same as ...
2
votes
2answers
72 views

Zeroes of polynomial

$$c_1,c_2 \text{ are polynomial's }g(x)=x^2+ax+b \text{ roots } \Leftrightarrow \begin{cases} g(c_1)=c_1^2+ac_1+b=0 \\ g(c_2)=c_2^2+ac_2+b=0 \end{cases}$$ Prove that for every polynomial with integer ...
2
votes
0answers
32 views

Linear Independence of Powers of “roots vector” [duplicate]

Let us be working over the field of complex numbers. Suppose $f(x)= a_n x^n + \cdots +a_1 x + a_0$ is a degree $n$ polynomial with $n$ distinct roots $z_1,\ldots,z_n$. Is the following matrix always ...
0
votes
2answers
32 views

How to get the characteristic equation from a recurrence relation of this form?

I've been getting the characteristic equation from relations of the form $$U_n=3U_{n-1}-U_{n-3}$$ Thanks to this question I made before: How to get the characteristic equation? Now, I recently ...
2
votes
2answers
54 views

Uniform convergence of matrix integral sequence

I was given recursively defined: $M_k=I+\int_{t_0}^tA(s)M_{k-1}(s)~ds$ and $M_0=I$ and that $A(t)$ is a matrix with entries that are continuous functions on $t_0\leq t\leq t_1$. By induction we can ...
6
votes
0answers
154 views

Coefficients in expansion of $(\sqrt[3]{2} - 1)^m$

In trying to solve $a^3 - 2b^3 = 1$ over the integers I came across the need to answer the question: when does $(1+ \sqrt[3]{2} + \sqrt[3]{2}^2)^n$ have no $\sqrt[3]{2}^2$ term in it's expansion (in ...
0
votes
1answer
34 views

How to solve recurrence relation equations

How do I solve the following system equations? $x_i = 2x_{i-1} + 3x_{i-2}$, where $i = 1, 2, 3..., x_1 = 3$, and $x_2 = 6$. The answer is $x_i = \frac{3}{4}(3^i - (-1)^i)$. It's easy to solve: ...
1
vote
0answers
70 views

What is common between difference operators and recurent relations?

They say that solutions of recurrence relations are combinations of exponential functions, the series like [1 a a^2 a^3 and etc]. I know that the difference operators have a matrix like ...
0
votes
1answer
30 views

I have a recursively defined function, and another function involving powers of a matrix. How can I show that they are equal?

The problem is Let $A$ be the $n \times n$ adjacency matrix of a graph $G=(V,E)$ on $n$ vertices, i.e. $A=(a_{ij})$ and $$a_{ij}=\begin{cases} 1 & ij\in E \\ 0 & ij\notin E ...
2
votes
1answer
101 views

Basis for recurrence relation solutions

So, I have a question: Imagine a recurrence relation $U(n+2) = 2U(n+1) + U(n)$. How do I determine the dimension (and the vectors that constitute the basis) of a vector space which contains all ...
3
votes
1answer
78 views

Characterising spaces of linear recurrent sequences.

Let $K$ be a field and $\def\N{\mathbf N}K^\N$ the infinite dimensional space of all sequences of elements of$~K$. Any linear recurrence relation of order $d$ with constant coefficients $$ a_{i+d} = ...
9
votes
3answers
275 views

The integer $c_n$ in $(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$

For non-negative integer $n$, write $$(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$$ where $a_n,b_n,c_n$ are integers. For any non-negative integer $m$, prove or disprove ...
0
votes
1answer
117 views

Solving recursive relations using matrix method.

I am looking to solve the recursive relation $P_n=2P_{(n-2)}+3P_{(n-3)}+7P_{(n-7)}$ using the matrix method. The matrix method solves the recursive relation in ...
0
votes
1answer
47 views

Recipe for solving linear discrete-time model for which N(t) is influenced by N(u) and N(v) u<t, v<t.

For solving linear discrete time model of the form $$N_{t+1}=pN_{t}+c$$ (when saying solving I mean that $N_{t}$ is expressed only in function of $p$, $c$ and the initial conditions) one can first ...
0
votes
0answers
31 views

recurrence relation basis vectors

I see that recurrence $x_n + c_1 x_{n-1} + \cdots = 0$, which may also be written as $x^n + c_1 x^{n-1} + \cdots = 0$ has a solution in the terms of eigenvalue powers, $$x_n = x_{01} \lambda_1^n + ...
3
votes
1answer
108 views

What does $x_n = s\, x_{n-1}$ mean in the components of recurrence?

Say you have a reucrrence $x_{n+1} = 3x_n+2$. Though, it is a inhomogenous, it can be represented by a linear system $$\begin{bmatrix} x_{n+1}\\1\end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 0 & ...
2
votes
1answer
104 views

Recurrence Relation with Square Root

Well, I was doing a problem on recurrence relation , where there was given a an recurrence relation and we had to find $a_{n}$ or simplify the recurrence. The recurrence relation was $$\begin{align} ...
3
votes
1answer
145 views

Diagonalizing/eigenvalues of a particular infinite dimensional matrix

I have trying to show that the continuum limit of n quantum harmonic oscillators gives rise the the Klein-Gordon field. However, instead of a usual finite string, I want to do it on a ring. Assume $n ...
1
vote
2answers
35 views

Recursive formulae involving a linear operator

Given a basis $e_{1}$, $e_{2}$ in the plane, define the linear operator $F$ as $F(e_{1})=3e_{1}+e_{2}$ and $F(e_{2})=e_{2}$. Furthermore, define the sequence $u_{1},u_{2},\dots$ of vectors in the ...
1
vote
3answers
90 views

How to solve linear recurrences consisting of both $x_n$ and $y_n$?

I know how to solve a general linear, homogenous recurrence but these are the ones I've been given:(i) $x_{n+1} = 3x_n + 6y_n$(ii) $y_{n+1} = 6x_n - 2y_n$ Initial conditions: $x_0 = -1, y_0 = 0$ How ...
3
votes
1answer
49 views

Finding Determinants Recursively

From the MIT OCW Linear Algebra (18.06) final exam, question 9: For square matrices with 3's on the diagonal, 2s on the diagonal above, and 1s on the diagonal below: $$A_1=\begin{pmatrix} 3 ...
1
vote
2answers
389 views

Find a formula for the nth term of the sequence defined by the third-order recursion:

$t_{n+2} = 3t_{n+1} + 6t_n ā€“ 8t_{nā€“1}$ with initial values $t_0 = 3, t_1 = t_2 = ā€“6$ You don't have to give me the answer, please just try and point me in the right direction.
1
vote
2answers
582 views

Solving system of recurrence relations

Base Case: $$ \left\{ \begin{array}{c} T(1) = 1 \\ T(2) = 1 \\T(3) = 4\end{array} \right. $$ I have the system: $$ \left\{ \begin{array}{c} T(N) = G(N-1) + F(N-1) \\ G(N) = F(N-1) + G(N-1) \\ ...
0
votes
0answers
135 views

Given a state transformation matrix and a state vector, how to find the total number of changes for each individual element.

I have a vector of binary variables, $s$ representing a state at some point in time, and a transformation matrix $T$. The initial state is $s_0$. $s_n = Ts_{n-1}$ Given a number of transformations, ...
13
votes
6answers
998 views

How to solve this recurrence relation? $f_n = 3f_{n-1} + 12(-1)^n$

How to solve this particular recurrence relation ? $$f_n = 3f_{n-1} + 12(-1)^n,\quad f_1 = 0$$ such that $f_2 = 12, f_3 = 24$ and so on. I tried out a lot but due to $(-1)^n$ I am not able to ...
4
votes
2answers
300 views

Understanding why the roots of homogeneous difference equation must be eigenvalues

There is some obvious relationship between the root solutions to a homogeneous difference equation (as a recurrence relation) and eigenvalues which I'm trying to see. I have read over the wiki article ...
2
votes
3answers
116 views

recurrence solution to gambler's ruin

From DeGroot 2.4.2, let $a_i$ be the conditional probability that the gambler wins all $k$ given gambler is at $i$. $a_i = pa_{i+1} + (1 - p)a_{i-1} $ It's not clear from the text what steps are ...
0
votes
1answer
274 views

Solving Linear Systems with Singular Matrices

Good morning! For (say, homogenous) linear systems of the form $$x_{n+1} = A x_n,$$ where $A$ is a nonsingular matrix, each initial value problem can be solved by the method of finding a general ...
1
vote
2answers
133 views

Analyzing a recurrence relation given by a Toeplitz matrix

Let $p$ be an odd prime, and $M_p$ be the $p\times p$ Toeplitz matrix over $\mathbb{F}_2$ given by $a_0=a_1=1$ and $a_{-p+1}=1$, e.g. for $p=5$ we have $$M_5=\left[\begin{array}{ccccc} 1 & & ...
1
vote
1answer
173 views

Linear Recurrence of Matrix into Closed Form Example Explanation?

I was given the following as an example of a linear recurrence and I don't understand how it works... Let us call the following eq1: $$x_i = \begin{bmatrix} \sum_{z = 1}^i{zk^{z-1}} \\ (i+1)k^i \\ ...
3
votes
2answers
2k views

Linear Algebra: Finding a steady state matrix

Here is the problem: And here is what I tried to do: I tried doing it in my calculator and got that the answer is 40 and 160 as you keep multiplying PX. Can anyone point out what I'm doing wrong ...
3
votes
3answers
236 views

Common theory for Linear equations, linear ODEs and linear recurrence relations

In Linear equations, linear ODEs and linear recurrence relations, when solving homogeneous equations, there are a subspace of solutions, and when solving inhomogeneous equations, a particular ...
3
votes
3answers
317 views

Does the ratio of consecutive terms converge for all linear recursions?

Does $f(n+1)/f(n)$ converge as $n\rightarrow\infty$ for $f(n)$ defined by a linear recursion, for all linear recursions?