In the theory of univariate linear recurrences with constant coefficients, there is a general method of solving initial value problems based on characteristic polynomials. I would like to ask, if any similar method is known for multivariate linear recurrences with constant coefficients.

empalhaviyt

empalhaviyt

Open question

2022-08-14

Linear multivariate recurrences with constant coefficients
In the theory of univariate linear recurrences with constant coefficients, there is a general method of solving initial value problems based on characteristic polynomials. I would like to ask, if any similar method is known for multivariate linear recurrences with constant coefficients. E.g., if there is a general method for solving recurrences like this:
f ( n + 1 , m + 1 ) = 2 f ( n + 1 , m ) + 3 f ( n , m ) f ( n 1 , m ) , f ( n , 0 ) = 1 , f ( 0 , m ) = m + 2.
Moreover, is their any method for solving recurrences in several variables, when the recurrence goes only by one of the variables? E.g., recurrences like this:
f ( n + 1 , m ) = f ( n , 2 m ) + f ( n 1 , 0 ) , f ( 0 , m ) = m .
This second question is equivalent to the question, if there is a method of solving infinite systems of linear univariate recurrences with constant coefficients. That is, using these optics, the second recurrence becomes f m ( n + 1 ) = f 2 m ( n ) + f 0 ( n 1 ) , f m ( 0 ) = m , m = 0 , 1 , .
I am not interested in a solution of any specific recurrence, but in solving such recurrences in general, or at least in finding out some of the properties of possible solutions. For instance, for univariate linear recurrences, each solution has a form c 1 p 1 ( n ) z 1 n + + c k p k ( n ) z k n ,, where c i 's are constants, p i 's are polynomials and z i 's are complex numbers. Does any similar property hold for some class of recurrences similar to what I have written?
I have been googling a lot, but have found only methods for some very special cases (in monographs on partial difference equations, etc.), but nothing general enough. I am not asking for a detailed explanation of any method, but references to the literature would be helpful. I don't know much about transforms (like discrete Fourier transform or z-transform), but I found certain hints that there could be a method based on these techniques. Is it possible to develop something general enough using transform, i.e., is the study of transforms worth an effort (in the context of solving these types of recurrences)? However, it seems to me that the generalization of the characteristic polynomial method (perhaps, some operator-theoretic approach) could lead to more general results. Has there been any research on this topic?

Answer & Explanation

neglegir86

neglegir86

Beginner2022-08-15Added 12 answers

Step 1
Set up a bivariate generating function: G ( x , y ) = r , s f ( m , n ) x m y n and work from there like usual.
Step 2
For your recurrence ( n + 1 , m ) = f ( n , 2 m ) + f ( n 1 , 0 ) , f ( 0 , m ) = m change variable m = 2 r and work from there.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Research Methodology

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?