A sequence in which $x_n$ depends on all of $x_0, ... x_{n-1}$

Question

A particular combinatorial sequence I was looking at turned out to obey the following pair of recurrence relations:

$$N_{2n+1}=\sum^n_{k=0}N_{2k}$$ $$N_{2n}=\left(\sum^{n-1}_{k=0}N_{2k+1}\right)+1=\sum^n_{k=0}N_{2k-1}$$

For the second form of the second equation, I'm using the convention $N_{-1}=1$.

The even terms depend on the odd terms and vice versa, but by applying these relations twice and rearranging sums, we can express the odd members only in terms of previous odd members, and similarly for even members. I'll skip the details and focus on the odd terms as an example. Setting $x_n=N_{2n+1}$, we have (if my calculations are correct):

$$x_{n+1}=\sum^n_{i=-1}(n-i)x_i$$

Note that by definition $x_{-1}=N_{-1}=1$.

Are there any general methods for solving a recurrence such as this one, where each term depends on all previous terms?

Answer 1

You might have made a mistake in the expression for the odd terms. Now they have the form 1, 0, 1, 2, 4, 8, 16, 32, 64, ... and I think you would have recognized those numbers as powers of two. Nevertheless, I'll give an example derivation of this, to illustrate how generating functions work.

It's important that you know some basic power series expansions and that you're a little creative with them (you will get this by practicing). You also wanna make no mistakes (I usually screw up about four times until I finally get it right).

First, I transcribed the $x_n$'s you used to $a_k$'s, where $a_k = x_{k-1}$, so that $a_0 = 1$. This is more convenient when using generating functions, because you want to take a sum starting from zero. The idea is that you have a relation like yours: $$ a_k = \sum_{i=0}^{k-1}{(k - i - 1)a_i} $$ for $k > 0$

(this is the same relation as yours but using the variables $a_k$ like I explained)

Now we multiply both sides with $x^k$ and take the sum from zero to infinity, and define the sum to be equal to some undetermined function $f$: $$ f(x) := \sum_{k=0}^{\infty}{a_k x^k} = a_0 + \sum_{k=1}^{\infty}{\sum_{i=0}^{k-1}{(k - i - 1)a_i}x^k} $$

The term $a_0$ is outside the summation because the formula is only valid for $k > 0$ (I messed this part up a couple of times, it's important!).

Now I'm gonna speed it up a little. Bring the $a_0$ to the left. Split the inner term to $((k+1)x^k - (i + 2)x^k)a_i$. In the next step we're assuming that the series converges absolutely (if I'm not mistaken, this is the condition that is needed to swap the summations and still get the same result). Swap the summations (I always write the double summation as $\sum_{0\leq i<k}$, meaning "sum over all $i$, $k$ that satisfy this relation", as an intermediate step, as I've learned from the book "Concrete Mathematics"), then actually do this. After rearranging some terms, we get: $$ f(x) - a_0 = \sum_{i=0}^{\infty} \left[ (\sum_{k=i+1}^{\infty}{(k+1)x^k} ) - (i + 2)(\sum_{k=i+1}^{\infty}{x^k}) \right] $$

Noticing $(k+1)x^k = \frac{d}{dx} x^{k+1}$ and assuming that the conditions for $\sum_{k=i+1}^{\infty}{ \frac{d}{dx} x^{k+1} } = \frac{d}{dx} \sum_{k=i+1}^{\infty}{ x^{k+1} }$ are met, we can bring the derivative sign out of the summation. I hope you're able to sum the righthand side of that, else you can use wolfram alpha which I may or may not have used to calculate the derivative. Anyway, when summed and derived (is that a verb to describe taking a derivative?) this series and summed the other one, we end up with:

$$ f(x) - a_0 = -\sum_{i=0}^{\infty}{\left[a_ix^i(\frac{ix-i+x-2}{(1-x)^2} + \frac{i+2}{1-x})\right]} = \frac{x}{(1-x)^2}\sum_{i=0}^{\infty}{a_i x^{i+1}} $$ $$ = \frac{x^2}{(1-x)^2}f(x) $$

Subtracting $a_0$ from both sides, then multiplying with $(1-x)^2$ yields: $$ (1-x)^2(f(x) - a_0) = x^2f(x) $$ and after some algebraic manipulation we find: $$ f(x) = a_0 - \frac{a_0}{2}x + \frac{a_0}{2(1-2x)}x $$

If we substitute $y = 2x$ in $\frac{1}{1-y} = 1 + y + y^2 + ...$ we get $\frac{1}{1-2x} = 1 + 2x + 4x^2 + 8x^3 + ... + 2^kx^k + ...$. Using this, we can find the power series expansion of the function f(x) to be equal to $ \sum_{i = 0}^{\infty}{a_ix^i} $ where $a_1 = 0 $, $ a_i = 2^{i - 2}a_0$. This holds when we check it with the numbers that I manually calculated.

This is how such a recurrence can be solved with generating functions. It is not that easy and very error-prone, but I found the method to be working in suprisingly many cases. I have been working on the content in this post for a while. I hope it illustrates the approach well. If you want to become good with generating functions, I recommend reading generatingfunctionology and doing the exercises (I never did a lot of them, maybe that's why I screwed up so much when making this post...).

Answer 2

I noticed that the sequence $N$ seemed to follow a Fibanacci-type law:

$$N_n = N_{n-1} + N_{n-2},\quad n\geq4$$

We can verify this using the proven recurrence relations in the OP:

$$N_{2n+1}=\sum^n_{k=0}N_{2k}=N_{2n}+\sum^{n-1}_{k=0}N_{2k}=N_{2n}+N_{2n-1}$$

$$N_{2n}=\sum^n_{k=0}N_{2k-1}=N_{2n-1}+\sum^{n-1}_{k=0}N_{2k-1}=N_{2n-1}+N_{2n-2}$$

Why exactly this fails for $n<4$ I'm not sure, it might be some strange edge condition that slipped my mind when I was deriving my own recurrence relation. In any case, the OEIS confirms that this is indeed the sequence I was looking for: a comment states "For $n \geq 3$, also the number of vertex covers for the cycle graph $C_n$", which is equivalent to my own problem.