Hadamard product and binomial convolution of linear recurrences
source link: http://codeforces.com/blog/entry/103136
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Hi everyone!
Let be a ring, and be linear recurrence sequences, such that
In some applications, the following two sequences arise:
Today I'd like to write about the framework that allows to prove that both the sequences defined above are also linear recurrences. It would also allow to compute their characteristic polynomials in , which is optimal as their degrees are in both cases.
Umbral calculus
Generally, a linear recurrence can be described and analyzed with the help of the linear functional such that
For such functional, when is a multiple of the characteristic polynomial of . The existence of the characteristic polynomial is the criterion of being a linear recurrence. So, we need to prove that there is such a polynomial for defined above.
Joint umbral calculus
To analyze joint properties of and , we define a linear functional such that
Similarly to the case of a single recurrence, whenever is a linear combination of and , where
are the characteristic polynomials of and . In other words, whenever lies in the ideal .
Composed sum
For the binomial convolution let , then
To show that is a linear recurrence obeying to the rule
it is sufficient to show that there is a characteristics polynomial such that .
Assume that is an integral domain. Then the polynomial exists and can be defined explicitly as
where
The fact that is proven as follows:
In the sum above, there are summands, each of them is divisible by either or , so .
The polynomial defined above is called the composed sum of and .
Composed product
Now the question is, how to prove that the Hadamard product is a linear recurrence?
Using similar logic as above, one would define and then look for . Let
This one is a bit trickier to prove. Let's start with :
Rewriting it in the same way for arbitrary and , we get
Then the same logic applies as to in the binomial convolution case.
The polynomial defined above is called the composed product of and .
Computing composed products and sums
Let be the sum of -th powers of all and be the sum of -th powers of all , that is
The roots of the composed sum are for all and and of the composed product are , from which we can see that
So, if we're able to transform from to , then from to , compute the transforms above on them and then recover the characteristics polynomials from the result, it would solve the problem.
Next thing we should note is that the generating function of is
It can be further expanded as
where
is the reversed characteristic polynomial of . Its log-derivative is indeed
Finally, to inverse this transform, we could make use of the fact that , hence for
it holds that
The resulting has degree , so only terms of and are needed and they may be computed in .
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK