3
$\begingroup$

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?

  • 1
    Can you give information about what kind of terms are hidden by the $\ldots$? Another suggestion is that you give an actual example of an equation you care about.2011-09-17
  • 0
    @Srivatsan Narayanan Sure, I'll edit now, I wasn't sure it was relevant information (I know that there are alternative expressions for the relation in the question).2011-09-17
  • 3
    This is rather general. It's a bit like asking "Can integral equations always be solved?" For instance, if the sum doesn't occur in this linear fashion but as an argument of a non-linear function, things get more complicated -- did you intend to include that case? You might have to say more about the sort of cases you're interested to get answers that go beyond what's already there in the question you linked to.2011-09-17
  • 0
    @joriki Would a more focused question be something along the lines of: What conditions must a recurrence with a sum satisfy in order to rewrite it without the sum?2011-09-17
  • 1
    @all I wrote an answer. But I deleted it because, as joriki pointed out, the answer turned out to be just a solution of this particular equation. The question is, of course, more general than that.2011-09-17
  • 2
    @Robert: That would be an improvement, though I doubt you'd get a set of conditions that covers all cases -- I'd think more along the lines of whether there are other or broader classes of solvable recurrence relations involving summations beyond these strictly linear ones that can be solved using the methods described in the answers to the linked question. That's like the difference between asking "What are the conditions for a differential/integral equation to be solvable" and "What are some classes of differential/integral equations that are solvable".2011-09-17
  • 0
    @joriki Thanks for your insight, I will think about the question some more and try to reformulate it more appropriately.2011-09-17
  • 0
    For your recurrence, starting with $a_0=0, a_1=1,$ the odd number terms are perfect squares, and $\sqrt{a_n}=4\sqrt{a_{n-2}}-\sqrt{a_{n-4}}$. The series with square roots is shown in http://oeis.org/A0018352011-09-17
  • 0
    @Ross The intial conditions that correspond to my particular problem are $a_0=1$ and $a_1=2$. It is equivalent to [A006253.](http://oeis.org/A006253) Which gives the even terms as perfect squares and the odd terms as twice a perfect square. However, that really isn't the point of the question.2011-09-17
  • 0
    That's why I made it a comment. I made a spreadsheet and it looked neat. Your starting values offset the series by 1 (my $a_n$ is your $a_{n-1}$).2011-09-17
  • 0
    @Ross I hope I didn't offend. I should have seen that... The OEIS page gives two other recurrences that don't include the summation, but I couldn't naturally derive them from the particular problem that I was working on.2011-09-17

3 Answers 3

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.

  • 0
    The question was obviously ill-posed, thanks for your time.2011-09-17
0

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.

0

First reorganize the recurrence a bit, and write it without subtractions in indices: $$ a_{n + 2} = 2 a_{n + 1} + a_n + 4 \sum_{0 \le k \le n} a_k $$ If you define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$, and then recognize e.g. \begin{align} \sum_{n \ge 0} a_{n + r} z^n &= \frac{A(z) - a_0 - a_1 z - \ldots - a_{r - 1} z^{r - 1}}{z^r} \\ \sum_{n \ge 0} z^n \sum_{0 \le k \le n} a_k &= \frac{A(z)}{1 - z} \end{align} (For the last one, multiply $A(z)$ by $1/(1 - z) = 1 + z + z^2 + \ldots$). You'll get: $$ \frac{A(z) - a_0 - a_1 z}{z^2} = 2 \frac{A(z) - a_0}{z} + A(z) + 4 \frac{A(z)}{1 - z} $$ Written as partial fractions you have: $$ A(z) = \frac{a_1 - (2 a_1 - 3 a_0) z}{3 (1 - 4 z + z^2)} + \frac{3 a_0 - a_1}{3} \cdot \frac{1}{1 + z} $$ The zeros of the first denominator are $2 \pm \sqrt{3}$ so this gets ugly, and I'll leave it here.