Homogeneous and inhomogeneous recurrences for a sequence

Question

Some integer sequences have both homogeneous and inhomogeneous recurrence relations. If you know one, are there techniques for figuring out the other? (Or seeing if the other exists?) Below is an example and a related particular sequence I'm interested in.

The sequence OEIS A002620 satisfies $a(n) = 2a(n-1) - 2a(n-3) + a(n-4)$ and also $a(n) = a(n-2) + n - 1$, which is perhaps a nicer expression. It's easy to confirm that these both lead to the same generating function for the sequence. If you knew only one of them, could it help you find the other?

For an example without a known answer (at least not to the OEIS), the sequence A097701 satisfies \begin{align} a(n) =& \; 2a(n-1) + a(n-2) - 3a(n-3) - a(n-4) + a(n-5) + 3a(n-6) \\ & {}- a(n-7) - 2a(n-8) + a(n-9). \end{align} Does it also satisfy an inhomogeneous recurrence? (If so, hopefully of smaller degree.)

(Not essential to the question, but in case anyone's wondering: The two sequences are connected by interpretations concerning integer partitions. The first sequence counts partitions made with parts 2 and two kinds of 1s. The second sequence is the analogous count for allowed parts 3, two kinds of 2s, and two kinds of 1s.)

Answer 1

The question is

Some integer sequences have both homogeneous and inhomogeneous recurrence relations. If you know one, are there techniques for figuring out the other? (Or seeing if the other exists?)

In many cases of homogeneous recurrence relations there is the existence of a rational generating function.

For example, OEIS sequence A097701 has the g.f.

$$ A(x):=\frac1{(1-x)^2 (1-x^2)^2 (1-x^3)} = 1 + 2x + 5x^2 + \cdots. $$

Multiply this by a nontrivial factor of the denominator (if it exists)

$$ P(x):=(1-x) (1-x^2)^2 (1-x^3) = \\ 1 - x - 2 x^2 + x^3 + 2 x^4 + x^5 - 2 x^6 - x^7 + x^8 $$

to get

$$ A(x)P(x) = \frac1{1-x} = 1 + x + x^2 + x^3 + \cdots. $$

Thus, the sequence satisfies the inhomogeneous equation $$ a(n)=a(n-1)+2a(n-2)-a(n-3)-2a(n-4)-\\ a(n-5)+2a(n-6)+a(n-7)-a(n-8)+1. $$

Similar results come from other choices of $P(x)$. Also the procedure is reversible.

As an important special example, consider OEIS sequence A002620 "Quarter-squares" with g.f.

$$ A(x) = \frac{x^2}{(1-x)^3(1+x)} = x^2 + 2x^3 + 4x^4 + 6x^5 + \cdots. $$

Use seven polynomial divisors of the denominator to get recurrenes

\begin{align} a(n) &= -a(n-1) + n(n-1)/2, \\ a(n) &= a(n-1) + \lfloor n/2\rfloor, \\ a(n) &= a(n-2) + (n-1), \\ a(n) &= 2a(n-1) - a(n-2) + 1 - \text{mod}(n,2), \\ a(n) &= a(n-1) + a(n-2) - a(n-3) + 1, \\ a(n) &= 3a(n-1) - 3a(n-2) + a(n-3) + (-1)^n, \\ a(n) &= 2a(n-1) - 2a(n-3) + a(n-4). \end{align}

Answer 2

From the inhomogenoeus $a(n)=a(n-2)+n-1$ you get $a(n-1)=a(n-3)+n-2$; subtracting gives $a(n)-a(n-1)=a(n-2)-a(n-3)+1$. From that, you get $a(n-1)-a(n-2)=a(n-3)-a(n-4)+1$, and subtracting again gives $a(n)-2a(n-1)+a(n-2)=a(n-2)-2a(n-3)+a(n-4)$ which rearranges to $a(n)=2a(n-1)-2a(n-3)+a(n-4)$, which is your homogeneous.