Mixing
![Calculating the probability of an element being in 2 subsets [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Does there exist a nice closed form for multidimensional linear recurrence relations like those of single-dimensional ones?
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
If we have the recurrence relation
$$sum_j=0^k a_n-jc_j = 0$$
for all $ngeq k$ and $lambda_1,cdots,lambda_s$ are the (complex) roots of
$$P(lambda) = sum_j=0^k c_jlambda^j$$
with multiplicities $m_1,cdots,m_s$, then we may write
$$a_n = sum_i=1^s lambda_i^n Q_i(n),$$
where $Q_i(n)$ is a polynomial of degree at most $m_i-1$.
What if we have a recurrence of the form
$$sum_mathbfsin S c_mathbfsa_mathbfn-mathbfs = 0,$$
where $S$ is a set of vectors in $mathbbZ_geq 0^N$ and $mathbfninmathbbZ_geq 0^N$ so that each component of $mathbfn$ is $geq$ the corresponding component of any $mathbfsin S$. Can one find a similarly nice closed form for $a_mathbfn$, possibly using the zero set of
$$P(x_1,cdots,x_N) = sum_mathbfsin S c_mathbfs prod_i=1^N x_i^mathbfs_i?$$
I've been able to deduce that the generating function
$$f(x_1,cdots,x_N) = sum_mathbfninmathbbZ_geq 0^N a_mathbfnprod_i=1^N x_i^mathbfn_i$$
satisfies
$$f(x_1,cdots,x_N)P(x_1,cdots,x_N) = Q(x_1,cdots,x_N)$$
for some polynomial $Q$ with nonzero terms only at $prod_i=1^N x_i^mathbft_i$ for vectors $t$ that are $leq$ some element of $S$ in all components, with strict $<$ holding in at least one component - an analogue of the first step of solving a standard one-dimensional linear recurrence. But I'm afraid I can't figure out how to continue from here, or even if one can.
polynomials recurrence-relations
asked Aug 1 at 18:50
Carl Schildkraut
8,23711238
 |Â
show 2 more comments
up vote
2
down vote
favorite
If we have the recurrence relation
$$sum_j=0^k a_n-jc_j = 0$$
for all $ngeq k$ and $lambda_1,cdots,lambda_s$ are the (complex) roots of
$$P(lambda) = sum_j=0^k c_jlambda^j$$
with multiplicities $m_1,cdots,m_s$, then we may write
$$a_n = sum_i=1^s lambda_i^n Q_i(n),$$
where $Q_i(n)$ is a polynomial of degree at most $m_i-1$.
What if we have a recurrence of the form
$$sum_mathbfsin S c_mathbfsa_mathbfn-mathbfs = 0,$$
where $S$ is a set of vectors in $mathbbZ_geq 0^N$ and $mathbfninmathbbZ_geq 0^N$ so that each component of $mathbfn$ is $geq$ the corresponding component of any $mathbfsin S$. Can one find a similarly nice closed form for $a_mathbfn$, possibly using the zero set of
$$P(x_1,cdots,x_N) = sum_mathbfsin S c_mathbfs prod_i=1^N x_i^mathbfs_i?$$
I've been able to deduce that the generating function
$$f(x_1,cdots,x_N) = sum_mathbfninmathbbZ_geq 0^N a_mathbfnprod_i=1^N x_i^mathbfn_i$$
satisfies
$$f(x_1,cdots,x_N)P(x_1,cdots,x_N) = Q(x_1,cdots,x_N)$$
for some polynomial $Q$ with nonzero terms only at $prod_i=1^N x_i^mathbft_i$ for vectors $t$ that are $leq$ some element of $S$ in all components, with strict $<$ holding in at least one component - an analogue of the first step of solving a standard one-dimensional linear recurrence. But I'm afraid I can't figure out how to continue from here, or even if one can.
polynomials recurrence-relations
asked Aug 1 at 18:50
Carl Schildkraut
8,23711238
you have described (by dividing out by leading coefficient) the Markov type process $x_n+1 = M x_n$ with column vectors $x$ and square matrix $M.$ One may proceed by diagonalizing $P^-1MP$ and using revised vector..
– Will Jagy
Aug 1 at 19:42
I guess your $M$ has a special form as it also shifts the sequence by $1$
– Will Jagy
Aug 1 at 19:44
@WillJagy Thanks for your comment! I can't quite understand why this is true, however. What are the entries of your $x_i$, and how are you constructing $M$ from the recurrence?
– Carl Schildkraut
Aug 1 at 19:53
We can get the Fibonacci numbers with matrix $$ M = left( beginarraycc 1 & 1 \ 1 & 0endarrayright) $$ acting on column vector $$ left( beginarrayc x_n+1 \ x_n endarrayright) $$ to result in $$ left( beginarrayc x_n+2 \ x_n+1 endarrayright) $$ For this method, the matrix $M$ will always come out to be a "companion matrix" or transpose, depends on how we make choices.
– Will Jagy
Aug 1 at 19:57
1
@WillJagy Thanks! I think that idea very well might be adaptable; even though $mathbbZ^N$ and $mathbbZ$ are isomorphic, I don't believe one can turn a recurrence of this form into a simple standard linear recurrence (although using any standard bijection) we can transform it into a single 1D sequence. There might be some better way to one-dimensionally represent such a recurrence, however.
– Carl Schildkraut
Aug 1 at 20:26
 |Â
show 2 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
If we have the recurrence relation
$$sum_j=0^k a_n-jc_j = 0$$
for all $ngeq k$ and $lambda_1,cdots,lambda_s$ are the (complex) roots of
$$P(lambda) = sum_j=0^k c_jlambda^j$$
with multiplicities $m_1,cdots,m_s$, then we may write
$$a_n = sum_i=1^s lambda_i^n Q_i(n),$$
where $Q_i(n)$ is a polynomial of degree at most $m_i-1$.
What if we have a recurrence of the form
$$sum_mathbfsin S c_mathbfsa_mathbfn-mathbfs = 0,$$
where $S$ is a set of vectors in $mathbbZ_geq 0^N$ and $mathbfninmathbbZ_geq 0^N$ so that each component of $mathbfn$ is $geq$ the corresponding component of any $mathbfsin S$. Can one find a similarly nice closed form for $a_mathbfn$, possibly using the zero set of
$$P(x_1,cdots,x_N) = sum_mathbfsin S c_mathbfs prod_i=1^N x_i^mathbfs_i?$$
I've been able to deduce that the generating function
$$f(x_1,cdots,x_N) = sum_mathbfninmathbbZ_geq 0^N a_mathbfnprod_i=1^N x_i^mathbfn_i$$
satisfies
$$f(x_1,cdots,x_N)P(x_1,cdots,x_N) = Q(x_1,cdots,x_N)$$
for some polynomial $Q$ with nonzero terms only at $prod_i=1^N x_i^mathbft_i$ for vectors $t$ that are $leq$ some element of $S$ in all components, with strict $<$ holding in at least one component - an analogue of the first step of solving a standard one-dimensional linear recurrence. But I'm afraid I can't figure out how to continue from here, or even if one can.
polynomials recurrence-relations
asked Aug 1 at 18:50
Carl Schildkraut
8,23711238
If we have the recurrence relation
$$sum_j=0^k a_n-jc_j = 0$$
for all $ngeq k$ and $lambda_1,cdots,lambda_s$ are the (complex) roots of
$$P(lambda) = sum_j=0^k c_jlambda^j$$
with multiplicities $m_1,cdots,m_s$, then we may write
$$a_n = sum_i=1^s lambda_i^n Q_i(n),$$
where $Q_i(n)$ is a polynomial of degree at most $m_i-1$.
What if we have a recurrence of the form
$$sum_mathbfsin S c_mathbfsa_mathbfn-mathbfs = 0,$$
where $S$ is a set of vectors in $mathbbZ_geq 0^N$ and $mathbfninmathbbZ_geq 0^N$ so that each component of $mathbfn$ is $geq$ the corresponding component of any $mathbfsin S$. Can one find a similarly nice closed form for $a_mathbfn$, possibly using the zero set of
$$P(x_1,cdots,x_N) = sum_mathbfsin S c_mathbfs prod_i=1^N x_i^mathbfs_i?$$
I've been able to deduce that the generating function
$$f(x_1,cdots,x_N) = sum_mathbfninmathbbZ_geq 0^N a_mathbfnprod_i=1^N x_i^mathbfn_i$$
satisfies
$$f(x_1,cdots,x_N)P(x_1,cdots,x_N) = Q(x_1,cdots,x_N)$$
for some polynomial $Q$ with nonzero terms only at $prod_i=1^N x_i^mathbft_i$ for vectors $t$ that are $leq$ some element of $S$ in all components, with strict $<$ holding in at least one component - an analogue of the first step of solving a standard one-dimensional linear recurrence. But I'm afraid I can't figure out how to continue from here, or even if one can.
polynomials recurrence-relations
asked Aug 1 at 18:50
Carl Schildkraut
8,23711238
asked Aug 1 at 18:50
Carl Schildkraut
8,23711238
asked Aug 1 at 18:50
Carl Schildkraut
8,23711238
asked Aug 1 at 18:50
Carl Schildkraut
8,23711238
8,23711238
you have described (by dividing out by leading coefficient) the Markov type process $x_n+1 = M x_n$ with column vectors $x$ and square matrix $M.$ One may proceed by diagonalizing $P^-1MP$ and using revised vector..
– Will Jagy
Aug 1 at 19:42
I guess your $M$ has a special form as it also shifts the sequence by $1$
– Will Jagy
Aug 1 at 19:44
@WillJagy Thanks for your comment! I can't quite understand why this is true, however. What are the entries of your $x_i$, and how are you constructing $M$ from the recurrence?
– Carl Schildkraut
Aug 1 at 19:53
We can get the Fibonacci numbers with matrix $$ M = left( beginarraycc 1 & 1 \ 1 & 0endarrayright) $$ acting on column vector $$ left( beginarrayc x_n+1 \ x_n endarrayright) $$ to result in $$ left( beginarrayc x_n+2 \ x_n+1 endarrayright) $$ For this method, the matrix $M$ will always come out to be a "companion matrix" or transpose, depends on how we make choices.
– Will Jagy
Aug 1 at 19:57
1
@WillJagy Thanks! I think that idea very well might be adaptable; even though $mathbbZ^N$ and $mathbbZ$ are isomorphic, I don't believe one can turn a recurrence of this form into a simple standard linear recurrence (although using any standard bijection) we can transform it into a single 1D sequence. There might be some better way to one-dimensionally represent such a recurrence, however.
– Carl Schildkraut
Aug 1 at 20:26
 |Â
show 2 more comments
you have described (by dividing out by leading coefficient) the Markov type process $x_n+1 = M x_n$ with column vectors $x$ and square matrix $M.$ One may proceed by diagonalizing $P^-1MP$ and using revised vector..
– Will Jagy
Aug 1 at 19:42
I guess your $M$ has a special form as it also shifts the sequence by $1$
– Will Jagy
Aug 1 at 19:44
@WillJagy Thanks for your comment! I can't quite understand why this is true, however. What are the entries of your $x_i$, and how are you constructing $M$ from the recurrence?
– Carl Schildkraut
Aug 1 at 19:53
We can get the Fibonacci numbers with matrix $$ M = left( beginarraycc 1 & 1 \ 1 & 0endarrayright) $$ acting on column vector $$ left( beginarrayc x_n+1 \ x_n endarrayright) $$ to result in $$ left( beginarrayc x_n+2 \ x_n+1 endarrayright) $$ For this method, the matrix $M$ will always come out to be a "companion matrix" or transpose, depends on how we make choices.
– Will Jagy
Aug 1 at 19:57
1
@WillJagy Thanks! I think that idea very well might be adaptable; even though $mathbbZ^N$ and $mathbbZ$ are isomorphic, I don't believe one can turn a recurrence of this form into a simple standard linear recurrence (although using any standard bijection) we can transform it into a single 1D sequence. There might be some better way to one-dimensionally represent such a recurrence, however.
– Carl Schildkraut
Aug 1 at 20:26
you have described (by dividing out by leading coefficient) the Markov type process $x_n+1 = M x_n$ with column vectors $x$ and square matrix $M.$ One may proceed by diagonalizing $P^-1MP$ and using revised vector..
– Will Jagy
Aug 1 at 19:42
you have described (by dividing out by leading coefficient) the Markov type process $x_n+1 = M x_n$ with column vectors $x$ and square matrix $M.$ One may proceed by diagonalizing $P^-1MP$ and using revised vector..
– Will Jagy
Aug 1 at 19:42
I guess your $M$ has a special form as it also shifts the sequence by $1$
– Will Jagy
Aug 1 at 19:44
I guess your $M$ has a special form as it also shifts the sequence by $1$
– Will Jagy
Aug 1 at 19:44
@WillJagy Thanks for your comment! I can't quite understand why this is true, however. What are the entries of your $x_i$, and how are you constructing $M$ from the recurrence?
– Carl Schildkraut
Aug 1 at 19:53
@WillJagy Thanks for your comment! I can't quite understand why this is true, however. What are the entries of your $x_i$, and how are you constructing $M$ from the recurrence?
– Carl Schildkraut
Aug 1 at 19:53
We can get the Fibonacci numbers with matrix $$ M = left( beginarraycc 1 & 1 \ 1 & 0endarrayright) $$ acting on column vector $$ left( beginarrayc x_n+1 \ x_n endarrayright) $$ to result in $$ left( beginarrayc x_n+2 \ x_n+1 endarrayright) $$ For this method, the matrix $M$ will always come out to be a "companion matrix" or transpose, depends on how we make choices.
– Will Jagy
Aug 1 at 19:57
We can get the Fibonacci numbers with matrix $$ M = left( beginarraycc 1 & 1 \ 1 & 0endarrayright) $$ acting on column vector $$ left( beginarrayc x_n+1 \ x_n endarrayright) $$ to result in $$ left( beginarrayc x_n+2 \ x_n+1 endarrayright) $$ For this method, the matrix $M$ will always come out to be a "companion matrix" or transpose, depends on how we make choices.
– Will Jagy
Aug 1 at 19:57
1
1
@WillJagy Thanks! I think that idea very well might be adaptable; even though $mathbbZ^N$ and $mathbbZ$ are isomorphic, I don't believe one can turn a recurrence of this form into a simple standard linear recurrence (although using any standard bijection) we can transform it into a single 1D sequence. There might be some better way to one-dimensionally represent such a recurrence, however.
– Carl Schildkraut
Aug 1 at 20:26
@WillJagy Thanks! I think that idea very well might be adaptable; even though $mathbbZ^N$ and $mathbbZ$ are isomorphic, I don't believe one can turn a recurrence of this form into a simple standard linear recurrence (although using any standard bijection) we can transform it into a single 1D sequence. There might be some better way to one-dimensionally represent such a recurrence, however.
– Carl Schildkraut
Aug 1 at 20:26
 |Â
show 2 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2869405%2fdoes-there-exist-a-nice-closed-form-for-multidimensional-linear-recurrence-relat%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
you have described (by dividing out by leading coefficient) the Markov type process $x_n+1 = M x_n$ with column vectors $x$ and square matrix $M.$ One may proceed by diagonalizing $P^-1MP$ and using revised vector..
– Will Jagy
Aug 1 at 19:42
I guess your $M$ has a special form as it also shifts the sequence by $1$
– Will Jagy
Aug 1 at 19:44
@WillJagy Thanks for your comment! I can't quite understand why this is true, however. What are the entries of your $x_i$, and how are you constructing $M$ from the recurrence?
– Carl Schildkraut
Aug 1 at 19:53
We can get the Fibonacci numbers with matrix $$ M = left( beginarraycc 1 & 1 \ 1 & 0endarrayright) $$ acting on column vector $$ left( beginarrayc x_n+1 \ x_n endarrayright) $$ to result in $$ left( beginarrayc x_n+2 \ x_n+1 endarrayright) $$ For this method, the matrix $M$ will always come out to be a "companion matrix" or transpose, depends on how we make choices.
– Will Jagy
Aug 1 at 19:57
1
@WillJagy Thanks! I think that idea very well might be adaptable; even though $mathbbZ^N$ and $mathbbZ$ are isomorphic, I don't believe one can turn a recurrence of this form into a simple standard linear recurrence (although using any standard bijection) we can transform it into a single 1D sequence. There might be some better way to one-dimensionally represent such a recurrence, however.
– Carl Schildkraut
Aug 1 at 20:26