8
$\begingroup$

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}$.

$\endgroup$

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 28, 2018 at 5:12
4
$\begingroup$

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\in\mathbb{N}\ \text{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}$.

$\endgroup$
2
  • 1
    $\begingroup$ Note that $S(k,l)$ is just the binomial coefficient $\binom{k+l-1}{l}$. $\endgroup$ Nov 28, 2018 at 7:38
  • $\begingroup$ @VictorProtsak Yes, this was left out in the answer. It will be added. $\endgroup$ Nov 28, 2018 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.