Summation in a recurrence relation

Question

edited to reflect advice from the comments:

While working on a generalization of a tiling problem, I generated a recurrence relation to describe the total number of possible tilings. The relation contains a summation term: $a_n= 2a_{n-1}+a_{n-2}+ 4\sum\limits_{j=2}^n a_{n-j}$. I see from the answers to this question that such relations do occur and there exist several methods to solve them. Specifically, it appears that as long as the recurrence is linear, translating a given relation with a sum into one without a sum is fairly straightforward.

My question is: are there other classes of recurrence relations that also permit us to algebraically dispose of summations if they occur in the relation?

Answer 1

The question is vague, here is a short answer: use generating functions, as explained in the book generatingfunctionology by Herb Wilf (available at the author's website). Reading the 20 pages of the first chapter (Introductory ideas and examples) should give you an idea of the extent of what can be done.

Answer 2

On this particular problem, you can find $$a_n-a_{n-1}= 2a_{n-1}+a_{n-2}+ 4\sum\limits_{j=2}^n a_{n-j} - 2a_{n-2} - a_{n-3} - 4\sum\limits_{j=2}^{n-1} a_{n-1-j} = 2a_{n-1}+3a_{n-2}-a_{n-3}$$ so $$a_n= 3a_{n-1}+3a_{n-2}-a_{n-3}$$ which is one of the recurrences in OEIS A006253, implying that the denominator of the generating function is $1-3x-3x^2+x^3$ or some factor of it, such as $1+x$ or $1-4x+x^2$.

In general, this is an art rather than a science, and sometimes you will be lucky and can simplify a complicated recurrence. Sometimes you cannot.