  Let $R$ be a commutative ring and let $n \geq 1.$ We study $\Gamma(s)$, the
generating function and Ann$(s)$, the ideal of characteristic polynomials of
$s$, an $n$--dimensional sequence over $R$.
  We express $f(X_1,\ldots,X_n) \cdot \Gamma(s)(X_1^{-1},\ldots ,X_n^{-1})$ as
a partitioned sum. That is, we give (i) a $2^n$--fold ``border'' partition (ii)
an explicit expression for the product as a $2^n$--fold sum; the support of
each summand is contained in precisely one member of the partition. A key
summand is $\beta_0(f,s)$, the ``border polynomial'' of $f$ and $s$, which is
divisible by $X_1\cdots X_n$.
  We say that $s$ is {\em eventually rectilinear} if the elimination ideals
Ann$(s)\cap R[X_i]$ contain an $f_i(X_i)$ for $1 \leq i \leq n$. In this case,
we show that $\mbox{Ann}(s)$ is the ideal quotient $(\sum_{i=1}^n(f_i)\ :\
\beta_0(f,s)/(X_1\cdots X_n)).$
  When $R$ and $R[[X_1,X_2, \ldots ,X_n]]$ are factorial domains (e.g. $R$ a
principal ideal domain or ${\Bbb F}[X_1,\ldots,X_n]$), we compute {\em the
monic generator} $\gamma _i$ of $\mbox{Ann}(s) \cap R[X_i]$ from known $f_i \in
\mbox{Ann}(s) \cap R[X_i]$ or from a finite number of $1$--dimensional linear
recurring sequences over $R$. Over a field ${\Bbb F}$ this gives an
$O(\prod_{i=1}^n \delta \gamma _i^3)$ algorithm to compute an ${\Bbb F}$--basis
for $\mbox{Ann}(s)$.
