12
votes
4answers
342 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 ...
3
votes
2answers
99 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 ...
0
votes
1answer
26 views

Changing recurrence to matrix

$$F(x) = aF(x-k+1) + bF(x-k+2) + cF(x-k+4) + dF(x-k+7)$$ where $F(x) = 1$ if $x<k$. $a,b,c,d,k$ are known (and positive) and $x$ is chosen. Can anyone show how to set this up in matrix form ...
1
vote
1answer
52 views

How to convert this equation into a matrix form

$$F(x)=aF(x-k+1)+bF(x-k+2)+cF(x-k+4)$$ where $F(x)=1$ if $x<k$. $a,b,c,k$ are known (and positive) and $x$ is chosen. I want to solve this recurrence using a matrix but don't really know how to ...
0
votes
1answer
66 views

number of ways to fill a 2D grid

We have a 2D grid with n rows and m columns, we can fill it with numbers between 1 and k (both inclusive). Only condition is that for each r such that 1<=r<=k ,no two rows must have exactly the ...
2
votes
2answers
105 views

Internet problem solving contest question

I am trying to solve a problem from the IPSC http://ipsc.ksp.sk/2001/real/problems/f.html It basically asks to compute the following recursion. ...
2
votes
1answer
26 views

Find a direct way to calculate recursive elements (simple problem with matrices)

I nearly solved this question, I just need a hand with the last part since it is a bit confusing. We are given the recursive sequences $\{a_n\}$ and $\{b_n\}$ like this: $a_1=1$, $b_1=2$ ...
0
votes
1answer
99 views

Find a recurrent relation and generating function for the sequence

Let An be the nn matrix which has 1's on the leading diagonal and on the diagonals immediatle above and below the leading diagonal. Let an = det(An). Find a recurrent relation and generating ...
1
vote
1answer
87 views

Matrix powers and recurrence relations

The nth Fibonacci number can be found by raising the matrix $\begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix}$ to the nth power. Are there other recurrence formulas that can be solved like this? ...
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 ...
1
vote
0answers
87 views

Scaling for characteristic polynomial of sequence of growing matrices

This is a follow-up question to Limit of sequence of growing matrices. There I was considering a sequence of matrices defined by $$ K_L = \left[H\otimes I_{2^{L-2}}\right]\left[I_2 \otimes ...
5
votes
2answers
63 views

Let $A$ be a matrix sized $p\times p$, where $2\le p$. Using recurrence relations, describe $A^k$.

Let $A$ be a matrix sized $p\times p$, Where $2\le p$. The matrix values in the main diagonal are $0$ and the rest are $1$'s. Example for $A$ where $p=5$: $$\begin{bmatrix} 0 & 1 & 1 & 1 ...
1
vote
3answers
97 views

How to solve two recurrences dependent on each other

Let $F_n = a_1*F_{n-1} + b_1*F_{n-2} + c_1*G_{n-3}$ $G_n = a_2*G_{n-1} + b_2*G_{n-2} + c_2*F_{n-3}$ We are given $ a_1,b_1,c_1,a_2,b_2,c_2$ and $ F_0,F_1,F_2, G_0, G_1,G_2 $. We have to calculate ...
8
votes
1answer
213 views

Möbius function from random number sequence

Consider some arbitrary number sequence like the decimal expansion of $\pi$ = {3, 1, 4, 1, 5, 9, 2}. Prepend the sequence with the number $1$ so that you get {1, 3, 1, 4, 1, 5, 9, 2}. Then plug it ...
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, ...
3
votes
1answer
62 views

Powers of $2 \times 2$ matrices expressed in linear form

I recently reopened an old high school math textbook and came upon the matrices unit. Some of the questions were those rewrite-in-linear-form problems: given, say, $M^2 = 2M - I$, express in linear ...
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 \\ ...
1
vote
1answer
200 views

Matrix recurrence equation

We define a $"2 \times 2"$matrix $A$. The following recurrence equation is given:$$A^{k+1}=\frac{A^k}{k}+I,(k=1,N)$$where $I$ is the identity matrix. How can I find the matrix $A$? Thanks
2
votes
2answers
598 views

Recurrence for a lagged Fibonacci sequence

I know how to do the matrix for the standard $f(n) = f(n-1) + f(n-2)$ relationship, but what if it's piecewise? For instance, $f(1)$ through $f(30)$ have some preset values, and then for $f(31)$ ...
2
votes
2answers
143 views

Computation of characteristic polynomial fails for me

For a matrix $A\in\mathbb{K}^{n\times n}$ where $\mathbb{K}\in\{\mathbb{R},\mathbb{C}\}$ the characteristic polynomial is defined as $$\chi_A(\lambda) := \text{det}(A-\lambda I_n) = \sum_{k=0}^n c_k ...
1
vote
2answers
590 views

Matrix Exponentiation for Recurrence Relations

I know how to use Matrix Exponentiation to solve problems having linear Recurrence relations (for example Fibonacci sequence). I would like to know, can we use it for linear recurrence in more than ...