linear recurrence relation for square of sequence given recursively
up vote
6
down vote
favorite
If $a_n$ satisfies the linear recurrence relation $a_n = sum_{i=1}^k c_i a_{n-i}$ for some constants $c_i$, then is there an easy way to find a linear recurrence relation for $b_n = a_n^2$ ?
For example, if $a_n = a_{n-1} + a_{n-3}$, then $b_n=a_n^2$ seems to satisfy $b_n=b_{n-1}+b_{n-2}+3b_{n-3}+b_{n-4}-b_{n-5}-b_{n-6}$.
co.combinatorics
New contributor
add a comment |
up vote
6
down vote
favorite
If $a_n$ satisfies the linear recurrence relation $a_n = sum_{i=1}^k c_i a_{n-i}$ for some constants $c_i$, then is there an easy way to find a linear recurrence relation for $b_n = a_n^2$ ?
For example, if $a_n = a_{n-1} + a_{n-3}$, then $b_n=a_n^2$ seems to satisfy $b_n=b_{n-1}+b_{n-2}+3b_{n-3}+b_{n-4}-b_{n-5}-b_{n-6}$.
co.combinatorics
New contributor
add a comment |
up vote
6
down vote
favorite
up vote
6
down vote
favorite
If $a_n$ satisfies the linear recurrence relation $a_n = sum_{i=1}^k c_i a_{n-i}$ for some constants $c_i$, then is there an easy way to find a linear recurrence relation for $b_n = a_n^2$ ?
For example, if $a_n = a_{n-1} + a_{n-3}$, then $b_n=a_n^2$ seems to satisfy $b_n=b_{n-1}+b_{n-2}+3b_{n-3}+b_{n-4}-b_{n-5}-b_{n-6}$.
co.combinatorics
New contributor
If $a_n$ satisfies the linear recurrence relation $a_n = sum_{i=1}^k c_i a_{n-i}$ for some constants $c_i$, then is there an easy way to find a linear recurrence relation for $b_n = a_n^2$ ?
For example, if $a_n = a_{n-1} + a_{n-3}$, then $b_n=a_n^2$ seems to satisfy $b_n=b_{n-1}+b_{n-2}+3b_{n-3}+b_{n-4}-b_{n-5}-b_{n-6}$.
co.combinatorics
co.combinatorics
New contributor
New contributor
New contributor
asked Nov 28 at 3:56
Erich Friedman
311
311
New contributor
New contributor
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
5
down vote
Yes. Take the companion matrix $M$ of the characteristic polynomial of your original recurrence. Then the squared recurrence satisfies a recurrence with the characteristic polynomial of the symmetric square $S^2(M)$ of $M$. If the original recurrence has order $n$ this new recurrence has order ${n+1 choose 2}$, and its coefficients are polynomials (depending only on $n$) in the coefficients of the old recurrence.
To prove this it suffices to consider the case where the characteristic polynomial has distinct roots, by a density argument. Then $a_n$ is a linear combination of the sequences $lambda_i^n$ where $lambda_i$ are the roots of the characteristic polynomial. So $a_n^2$ is a linear combination of the sequences $(lambda_i lambda_j)^n$ (and we may have $i = j$), and $S^2(M)$ has the $lambda_i lambda_j$ as its eigenvalues. In general these are all also distinct, so the characteristic polynomial of $S^2(M)$ is minimal with this property and it's not possible to reduce the order further than this in general.
The same argument shows that for $k^{th}$ powers we can use the symmetric powers $S^k(M)$, and that for general products $a_n b_n$ of sequences satisfying linear recurrences we can use tensor / Kronecker products of the companion matrices of their characteristic polynomials.
1
Qiaochu has given explicit computations here. I would like to add that the equivalence (linear recurrence <-> rational generating series) is credited to Kronecker by A. Connes in Noncommutative Geometry.
– Duchamp Gérard H. E.
Nov 28 at 5:12
add a comment |
up vote
3
down vote
T. Brown and P.J. Shiue's paper here might be of interest as a first reference. In the introduction they mention that if $a_n$ is a second-order sequence then the sequence
of squares $a_{n}^2$ is a third-order sequence. They go on to show necessary conditions for the squares sequence to be a second-order sequence when $a_n$ is a homogeneous sequence.
In the paper of Cooper and Kennedy here, (section 5) they give an order six linear recurrence relation for the square of a third order linear recurrence relation (as appears in your example):
$$x^2_n = (a^2 + b)x^2_{n−1} + (a^2b + b^2 + ac)x^2_{n−2} + (a^3c + 4abc − b^3 +2c^2)x^2_{n−3}+(−ab^2c + a^2c^2 − bc^2)x^2_{n−4} + (b^2c^2 − ac^3)x^2_{n−5} − c^4x^2_{n−6}$$
where $x_n = ax_{n−1} + bx_{n−2} + cx_{n−3}$.
For similar questions where squares have been replaced with higher powers, the paper here by Stinchcombe might be interesting.
Edit: Qiaochu Yuan has provided the correct order for squares. Higher powers are addressed using the same argument in Theorem 3 of Stinchcombe's paper above. For convenience it is stated here:
Question: For what order does $y_{n} =x^l_{n}$ satisfy a linear recurrence relation, for $x_{n}$ a recurrence relation of order $k$?
A recurrence equation exists and the degree of the corresponding characteristic polynomial for the recurrence is counted by the
number of elements in $B_{l}$, where
$$ B_{l} = {(i_{1},...,i_{k}) | text{ each }i_j text{ is a nonnegative integer and } i_1+...+i_{k}=l }.$$
Given a value of $k$, define $S(k, l) =|B_{l}|$, then
Theorem 3: $S(k, l)$ obeys the relations: $S(k, l) = k$ for all $k$, $S(1, l) = l$ for all $l$, and $S(k,l) =S(k-1,l) + S(k, l-1)$ for every $k$ and $l$. Equivalently, $S(k, l)=binom{k+l-1}{l}$.
1
Note that $S(k,l)$ is just the binomial coefficient $binom{k+l-1}{l}$.
– Victor Protsak
Nov 28 at 7:38
@VictorProtsak Yes, this was left out in the answer. It will be added.
– Josiah Park
Nov 28 at 7:40
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
Yes. Take the companion matrix $M$ of the characteristic polynomial of your original recurrence. Then the squared recurrence satisfies a recurrence with the characteristic polynomial of the symmetric square $S^2(M)$ of $M$. If the original recurrence has order $n$ this new recurrence has order ${n+1 choose 2}$, and its coefficients are polynomials (depending only on $n$) in the coefficients of the old recurrence.
To prove this it suffices to consider the case where the characteristic polynomial has distinct roots, by a density argument. Then $a_n$ is a linear combination of the sequences $lambda_i^n$ where $lambda_i$ are the roots of the characteristic polynomial. So $a_n^2$ is a linear combination of the sequences $(lambda_i lambda_j)^n$ (and we may have $i = j$), and $S^2(M)$ has the $lambda_i lambda_j$ as its eigenvalues. In general these are all also distinct, so the characteristic polynomial of $S^2(M)$ is minimal with this property and it's not possible to reduce the order further than this in general.
The same argument shows that for $k^{th}$ powers we can use the symmetric powers $S^k(M)$, and that for general products $a_n b_n$ of sequences satisfying linear recurrences we can use tensor / Kronecker products of the companion matrices of their characteristic polynomials.
1
Qiaochu has given explicit computations here. I would like to add that the equivalence (linear recurrence <-> rational generating series) is credited to Kronecker by A. Connes in Noncommutative Geometry.
– Duchamp Gérard H. E.
Nov 28 at 5:12
add a comment |
up vote
5
down vote
Yes. Take the companion matrix $M$ of the characteristic polynomial of your original recurrence. Then the squared recurrence satisfies a recurrence with the characteristic polynomial of the symmetric square $S^2(M)$ of $M$. If the original recurrence has order $n$ this new recurrence has order ${n+1 choose 2}$, and its coefficients are polynomials (depending only on $n$) in the coefficients of the old recurrence.
To prove this it suffices to consider the case where the characteristic polynomial has distinct roots, by a density argument. Then $a_n$ is a linear combination of the sequences $lambda_i^n$ where $lambda_i$ are the roots of the characteristic polynomial. So $a_n^2$ is a linear combination of the sequences $(lambda_i lambda_j)^n$ (and we may have $i = j$), and $S^2(M)$ has the $lambda_i lambda_j$ as its eigenvalues. In general these are all also distinct, so the characteristic polynomial of $S^2(M)$ is minimal with this property and it's not possible to reduce the order further than this in general.
The same argument shows that for $k^{th}$ powers we can use the symmetric powers $S^k(M)$, and that for general products $a_n b_n$ of sequences satisfying linear recurrences we can use tensor / Kronecker products of the companion matrices of their characteristic polynomials.
1
Qiaochu has given explicit computations here. I would like to add that the equivalence (linear recurrence <-> rational generating series) is credited to Kronecker by A. Connes in Noncommutative Geometry.
– Duchamp Gérard H. E.
Nov 28 at 5:12
add a comment |
up vote
5
down vote
up vote
5
down vote
Yes. Take the companion matrix $M$ of the characteristic polynomial of your original recurrence. Then the squared recurrence satisfies a recurrence with the characteristic polynomial of the symmetric square $S^2(M)$ of $M$. If the original recurrence has order $n$ this new recurrence has order ${n+1 choose 2}$, and its coefficients are polynomials (depending only on $n$) in the coefficients of the old recurrence.
To prove this it suffices to consider the case where the characteristic polynomial has distinct roots, by a density argument. Then $a_n$ is a linear combination of the sequences $lambda_i^n$ where $lambda_i$ are the roots of the characteristic polynomial. So $a_n^2$ is a linear combination of the sequences $(lambda_i lambda_j)^n$ (and we may have $i = j$), and $S^2(M)$ has the $lambda_i lambda_j$ as its eigenvalues. In general these are all also distinct, so the characteristic polynomial of $S^2(M)$ is minimal with this property and it's not possible to reduce the order further than this in general.
The same argument shows that for $k^{th}$ powers we can use the symmetric powers $S^k(M)$, and that for general products $a_n b_n$ of sequences satisfying linear recurrences we can use tensor / Kronecker products of the companion matrices of their characteristic polynomials.
Yes. Take the companion matrix $M$ of the characteristic polynomial of your original recurrence. Then the squared recurrence satisfies a recurrence with the characteristic polynomial of the symmetric square $S^2(M)$ of $M$. If the original recurrence has order $n$ this new recurrence has order ${n+1 choose 2}$, and its coefficients are polynomials (depending only on $n$) in the coefficients of the old recurrence.
To prove this it suffices to consider the case where the characteristic polynomial has distinct roots, by a density argument. Then $a_n$ is a linear combination of the sequences $lambda_i^n$ where $lambda_i$ are the roots of the characteristic polynomial. So $a_n^2$ is a linear combination of the sequences $(lambda_i lambda_j)^n$ (and we may have $i = j$), and $S^2(M)$ has the $lambda_i lambda_j$ as its eigenvalues. In general these are all also distinct, so the characteristic polynomial of $S^2(M)$ is minimal with this property and it's not possible to reduce the order further than this in general.
The same argument shows that for $k^{th}$ powers we can use the symmetric powers $S^k(M)$, and that for general products $a_n b_n$ of sequences satisfying linear recurrences we can use tensor / Kronecker products of the companion matrices of their characteristic polynomials.
edited Nov 28 at 7:28
Alexey Ustinov
6,58245778
6,58245778
answered Nov 28 at 4:51
Qiaochu Yuan
76.3k25315596
76.3k25315596
1
Qiaochu has given explicit computations here. I would like to add that the equivalence (linear recurrence <-> rational generating series) is credited to Kronecker by A. Connes in Noncommutative Geometry.
– Duchamp Gérard H. E.
Nov 28 at 5:12
add a comment |
1
Qiaochu has given explicit computations here. I would like to add that the equivalence (linear recurrence <-> rational generating series) is credited to Kronecker by A. Connes in Noncommutative Geometry.
– Duchamp Gérard H. E.
Nov 28 at 5:12
1
1
Qiaochu has given explicit computations here. I would like to add that the equivalence (linear recurrence <-> rational generating series) is credited to Kronecker by A. Connes in Noncommutative Geometry.
– Duchamp Gérard H. E.
Nov 28 at 5:12
Qiaochu has given explicit computations here. I would like to add that the equivalence (linear recurrence <-> rational generating series) is credited to Kronecker by A. Connes in Noncommutative Geometry.
– Duchamp Gérard H. E.
Nov 28 at 5:12
add a comment |
up vote
3
down vote
T. Brown and P.J. Shiue's paper here might be of interest as a first reference. In the introduction they mention that if $a_n$ is a second-order sequence then the sequence
of squares $a_{n}^2$ is a third-order sequence. They go on to show necessary conditions for the squares sequence to be a second-order sequence when $a_n$ is a homogeneous sequence.
In the paper of Cooper and Kennedy here, (section 5) they give an order six linear recurrence relation for the square of a third order linear recurrence relation (as appears in your example):
$$x^2_n = (a^2 + b)x^2_{n−1} + (a^2b + b^2 + ac)x^2_{n−2} + (a^3c + 4abc − b^3 +2c^2)x^2_{n−3}+(−ab^2c + a^2c^2 − bc^2)x^2_{n−4} + (b^2c^2 − ac^3)x^2_{n−5} − c^4x^2_{n−6}$$
where $x_n = ax_{n−1} + bx_{n−2} + cx_{n−3}$.
For similar questions where squares have been replaced with higher powers, the paper here by Stinchcombe might be interesting.
Edit: Qiaochu Yuan has provided the correct order for squares. Higher powers are addressed using the same argument in Theorem 3 of Stinchcombe's paper above. For convenience it is stated here:
Question: For what order does $y_{n} =x^l_{n}$ satisfy a linear recurrence relation, for $x_{n}$ a recurrence relation of order $k$?
A recurrence equation exists and the degree of the corresponding characteristic polynomial for the recurrence is counted by the
number of elements in $B_{l}$, where
$$ B_{l} = {(i_{1},...,i_{k}) | text{ each }i_j text{ is a nonnegative integer and } i_1+...+i_{k}=l }.$$
Given a value of $k$, define $S(k, l) =|B_{l}|$, then
Theorem 3: $S(k, l)$ obeys the relations: $S(k, l) = k$ for all $k$, $S(1, l) = l$ for all $l$, and $S(k,l) =S(k-1,l) + S(k, l-1)$ for every $k$ and $l$. Equivalently, $S(k, l)=binom{k+l-1}{l}$.
1
Note that $S(k,l)$ is just the binomial coefficient $binom{k+l-1}{l}$.
– Victor Protsak
Nov 28 at 7:38
@VictorProtsak Yes, this was left out in the answer. It will be added.
– Josiah Park
Nov 28 at 7:40
add a comment |
up vote
3
down vote
T. Brown and P.J. Shiue's paper here might be of interest as a first reference. In the introduction they mention that if $a_n$ is a second-order sequence then the sequence
of squares $a_{n}^2$ is a third-order sequence. They go on to show necessary conditions for the squares sequence to be a second-order sequence when $a_n$ is a homogeneous sequence.
In the paper of Cooper and Kennedy here, (section 5) they give an order six linear recurrence relation for the square of a third order linear recurrence relation (as appears in your example):
$$x^2_n = (a^2 + b)x^2_{n−1} + (a^2b + b^2 + ac)x^2_{n−2} + (a^3c + 4abc − b^3 +2c^2)x^2_{n−3}+(−ab^2c + a^2c^2 − bc^2)x^2_{n−4} + (b^2c^2 − ac^3)x^2_{n−5} − c^4x^2_{n−6}$$
where $x_n = ax_{n−1} + bx_{n−2} + cx_{n−3}$.
For similar questions where squares have been replaced with higher powers, the paper here by Stinchcombe might be interesting.
Edit: Qiaochu Yuan has provided the correct order for squares. Higher powers are addressed using the same argument in Theorem 3 of Stinchcombe's paper above. For convenience it is stated here:
Question: For what order does $y_{n} =x^l_{n}$ satisfy a linear recurrence relation, for $x_{n}$ a recurrence relation of order $k$?
A recurrence equation exists and the degree of the corresponding characteristic polynomial for the recurrence is counted by the
number of elements in $B_{l}$, where
$$ B_{l} = {(i_{1},...,i_{k}) | text{ each }i_j text{ is a nonnegative integer and } i_1+...+i_{k}=l }.$$
Given a value of $k$, define $S(k, l) =|B_{l}|$, then
Theorem 3: $S(k, l)$ obeys the relations: $S(k, l) = k$ for all $k$, $S(1, l) = l$ for all $l$, and $S(k,l) =S(k-1,l) + S(k, l-1)$ for every $k$ and $l$. Equivalently, $S(k, l)=binom{k+l-1}{l}$.
1
Note that $S(k,l)$ is just the binomial coefficient $binom{k+l-1}{l}$.
– Victor Protsak
Nov 28 at 7:38
@VictorProtsak Yes, this was left out in the answer. It will be added.
– Josiah Park
Nov 28 at 7:40
add a comment |
up vote
3
down vote
up vote
3
down vote
T. Brown and P.J. Shiue's paper here might be of interest as a first reference. In the introduction they mention that if $a_n$ is a second-order sequence then the sequence
of squares $a_{n}^2$ is a third-order sequence. They go on to show necessary conditions for the squares sequence to be a second-order sequence when $a_n$ is a homogeneous sequence.
In the paper of Cooper and Kennedy here, (section 5) they give an order six linear recurrence relation for the square of a third order linear recurrence relation (as appears in your example):
$$x^2_n = (a^2 + b)x^2_{n−1} + (a^2b + b^2 + ac)x^2_{n−2} + (a^3c + 4abc − b^3 +2c^2)x^2_{n−3}+(−ab^2c + a^2c^2 − bc^2)x^2_{n−4} + (b^2c^2 − ac^3)x^2_{n−5} − c^4x^2_{n−6}$$
where $x_n = ax_{n−1} + bx_{n−2} + cx_{n−3}$.
For similar questions where squares have been replaced with higher powers, the paper here by Stinchcombe might be interesting.
Edit: Qiaochu Yuan has provided the correct order for squares. Higher powers are addressed using the same argument in Theorem 3 of Stinchcombe's paper above. For convenience it is stated here:
Question: For what order does $y_{n} =x^l_{n}$ satisfy a linear recurrence relation, for $x_{n}$ a recurrence relation of order $k$?
A recurrence equation exists and the degree of the corresponding characteristic polynomial for the recurrence is counted by the
number of elements in $B_{l}$, where
$$ B_{l} = {(i_{1},...,i_{k}) | text{ each }i_j text{ is a nonnegative integer and } i_1+...+i_{k}=l }.$$
Given a value of $k$, define $S(k, l) =|B_{l}|$, then
Theorem 3: $S(k, l)$ obeys the relations: $S(k, l) = k$ for all $k$, $S(1, l) = l$ for all $l$, and $S(k,l) =S(k-1,l) + S(k, l-1)$ for every $k$ and $l$. Equivalently, $S(k, l)=binom{k+l-1}{l}$.
T. Brown and P.J. Shiue's paper here might be of interest as a first reference. In the introduction they mention that if $a_n$ is a second-order sequence then the sequence
of squares $a_{n}^2$ is a third-order sequence. They go on to show necessary conditions for the squares sequence to be a second-order sequence when $a_n$ is a homogeneous sequence.
In the paper of Cooper and Kennedy here, (section 5) they give an order six linear recurrence relation for the square of a third order linear recurrence relation (as appears in your example):
$$x^2_n = (a^2 + b)x^2_{n−1} + (a^2b + b^2 + ac)x^2_{n−2} + (a^3c + 4abc − b^3 +2c^2)x^2_{n−3}+(−ab^2c + a^2c^2 − bc^2)x^2_{n−4} + (b^2c^2 − ac^3)x^2_{n−5} − c^4x^2_{n−6}$$
where $x_n = ax_{n−1} + bx_{n−2} + cx_{n−3}$.
For similar questions where squares have been replaced with higher powers, the paper here by Stinchcombe might be interesting.
Edit: Qiaochu Yuan has provided the correct order for squares. Higher powers are addressed using the same argument in Theorem 3 of Stinchcombe's paper above. For convenience it is stated here:
Question: For what order does $y_{n} =x^l_{n}$ satisfy a linear recurrence relation, for $x_{n}$ a recurrence relation of order $k$?
A recurrence equation exists and the degree of the corresponding characteristic polynomial for the recurrence is counted by the
number of elements in $B_{l}$, where
$$ B_{l} = {(i_{1},...,i_{k}) | text{ each }i_j text{ is a nonnegative integer and } i_1+...+i_{k}=l }.$$
Given a value of $k$, define $S(k, l) =|B_{l}|$, then
Theorem 3: $S(k, l)$ obeys the relations: $S(k, l) = k$ for all $k$, $S(1, l) = l$ for all $l$, and $S(k,l) =S(k-1,l) + S(k, l-1)$ for every $k$ and $l$. Equivalently, $S(k, l)=binom{k+l-1}{l}$.
edited Nov 28 at 7:49
answered Nov 28 at 4:06
Josiah Park
66914
66914
1
Note that $S(k,l)$ is just the binomial coefficient $binom{k+l-1}{l}$.
– Victor Protsak
Nov 28 at 7:38
@VictorProtsak Yes, this was left out in the answer. It will be added.
– Josiah Park
Nov 28 at 7:40
add a comment |
1
Note that $S(k,l)$ is just the binomial coefficient $binom{k+l-1}{l}$.
– Victor Protsak
Nov 28 at 7:38
@VictorProtsak Yes, this was left out in the answer. It will be added.
– Josiah Park
Nov 28 at 7:40
1
1
Note that $S(k,l)$ is just the binomial coefficient $binom{k+l-1}{l}$.
– Victor Protsak
Nov 28 at 7:38
Note that $S(k,l)$ is just the binomial coefficient $binom{k+l-1}{l}$.
– Victor Protsak
Nov 28 at 7:38
@VictorProtsak Yes, this was left out in the answer. It will be added.
– Josiah Park
Nov 28 at 7:40
@VictorProtsak Yes, this was left out in the answer. It will be added.
– Josiah Park
Nov 28 at 7:40
add a comment |
Erich Friedman is a new contributor. Be nice, and check out our Code of Conduct.
Erich Friedman is a new contributor. Be nice, and check out our Code of Conduct.
Erich Friedman is a new contributor. Be nice, and check out our Code of Conduct.
Erich Friedman is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f316374%2flinear-recurrence-relation-for-square-of-sequence-given-recursively%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown