linear recurrence and characteristic polynomial It is well known that if linear recurrences $u_n$ and $v_n$ have  characteristic polynomials $K_u$ and $K_v$, then $u_n + v_n$ has characteristic polynomial $K_u K_v$. Is the converse true? If my characteristic polynomial factors as $K_u K_v$, then can I find $u_n$ and $v_n$ such that my recurrence can be written as $u_n + v_n$?
 A: For the sake of closure, let me expand my comments into an answer.
The answer is "no"; but it becomes a "yes" if you assume $K_{u}$ and $K_{v}$
to be coprime. Before I start proving it, let me introduce my own notation,
which I believe is clearer than yours (specifically, I will avoid the use of
the nebulous notion of a "linear recurrence" and the easily misunderstood word
"characteristic polynomial").
Fix a field $F$. Set $\mathbb{N}=\left\{  0,1,2,\ldots\right\}  $. Let
$F^{\infty}$ be the set $\left\{  \left(  a_{0},a_{1},a_{2},\ldots\right)
\ \mid\ a_{i}\in F\text{ for each }i\in\mathbb{N}\right\}  $ of all infinite
sequences of elements of $F$. This set $F^{\infty}$ is an $F$-vector space
(where the operations are entrywise: e.g., we have $\left(  a_{0},a_{1}
,a_{2},\ldots\right)  +\left(  b_{0},b_{1},b_{2},\ldots\right)  =\left(
a_{0}+b_{0},a_{1}+b_{1},a_{2}+b_{2},\ldots\right)  $).

Definition. Let $P\in F\left[  X\right]  $ be a polynomial. Write $P$ in
  the form $P=\sum\limits_{i=0}^{k}p_{i}X^{i}$ for some $k\in\mathbb{N}$ and
  some $p_{0},p_{1},\ldots,p_{k}\in F$.
Let $\mathbf{a}=\left(  a_{0},a_{1},a_{2},\ldots\right)  \in F^{\infty}$ be a
  sequence. Then, we say that the sequence $\mathbf{a}$ is $P$-linearly
  recursive if and only if each $n\in\mathbb{N}$ satisfies $\sum\limits_{i=0}
^{k}p_{i}a_{n+i}=0$. (Notice that this definition does not depend on how
  precisely we represent $P$ in the form $\sum\limits_{i=0}^{k}p_{i}X^{i}$;
  indeed, any two such representations differ only in zero addends, and these
  zero addends do not change the sum $\sum\limits_{i=0}^{k}p_{i}a_{n+i}$.)

(My notion of a "$P$-linearly recursive sequence" roughly corresponds to your
"recursive sequence with characteristic polynomial $P$", but keep in mind that
$P$ is not uniquely determined by the sequence. For example, each $X$-linearly
recursive sequence is also $X^{2}$-linearly recursive.)

Theorem 1. Let $P$ and $Q$ be two coprime polynomials in the principal
  ideal domain $F\left[  X\right]  $. Let $\mathbf{a}\in F^{\infty}$ be a
  $PQ$-linearly recursive sequence. Then, $\mathbf{a}$ is the sum of a
  $P$-linearly recursive sequence with a $Q$-linearly recursive sequence.

Before we prove Theorem 1, we introduce a helpful $F\left[  X\right]  $-module
structure on $F^{\infty}$. Namely, let $S$ be the $F$-linear map
$F^{\infty}\rightarrow F^{\infty},\ \left(  a_{0},a_{1},a_{2},\ldots\right)
\mapsto\left(  a_{1},a_{2},a_{3},\ldots\right)  $.
This map $S$ is called the shift operator (since it shifts a sequence by $1$
forward, dropping the very first entry). It is easy to see that
\begin{equation}
S^{i}\left(  a_{0},a_{1},a_{2},\ldots\right)  =\left(  a_{0+i}
,a_{1+i},a_{2+i},\ldots\right)
\label{1}
\tag{1}
\end{equation}
for each $i\in\mathbb{N}$ and each $\left(  a_{0},a_{1},a_{2},\ldots\right)
\in F^{\infty}$.
Let $\operatorname*{End}\left(  F^{\infty}\right)  $ denote the $F$-algebra of
all endomorphisms of the $F$-vector space $F^{\infty}$. By the universal
property of the polynomial ring $F\left[  X\right]  $, there exists a unique
$F$-algebra homomorphism $\phi:F\left[  X\right]  \rightarrow
\operatorname*{End}\left(  F^{\infty}\right)  $ satisfying $\phi\left(
X\right)  =S$. Consider this $\phi$, and use it to make $F^{\infty}$ into an
$F\left[  X\right]  $-module. Thus, this $F\left[  X\right]  $-module
structure on $F^{\infty}$ satisfies $X\mathbf{a}=\underbrace{\phi\left(
X\right)  }_{=S}\mathbf{a}=S\mathbf{a}$ for each $\mathbf{a}\in F^{\infty}$.
We can now easily describe how any polynomial acts on $F^{\infty}$:

Proposition 2. Let $P\in F\left[  X\right]  $ be a polynomial. Write $P$
  in the form $P=\sum\limits_{i=0}^{k}p_{i}X^{i}$ for some $k\in\mathbb{N}$ and
  some $p_{0},p_{1},\ldots,p_{k}\in F$.
Let $\mathbf{a}=\left(  a_{0},a_{1},a_{2},\ldots\right)  \in F^{\infty}$ be a
  sequence. Then, $P\mathbf{a}=\left(  \sum\limits_{i=0}^{k}p_{i}a_{0+i}
,\sum\limits_{i=0}^{k}p_{i}a_{1+i},\sum\limits_{i=0}^{k}p_{i}a_{2+i}
,\ldots\right)  $.

Proof of Proposition 2. We have $\mathbf{a}=\left(  a_{0},a_{1},a_{2}
,\ldots\right)  $. Hence, each $i\in\mathbb{N}$ satisfies
\begin{equation}
S^{i}\mathbf{a}=S^{i}\left(  a_{0},a_{1},a_{2},\ldots\right)
=\left(  a_{0+i},a_{1+i},a_{2+i},\ldots\right)
\label{2}
\tag{2}
\end{equation}
(by \eqref{1}). On the other hand, applying the map $\phi$ to the equality
$P=\sum\limits_{i=0}^{k}p_{i}X^{i}$, we obtain
$\phi\left(  P\right)  =\phi\left(  \sum\limits_{i=0}^{k}p_{i}X^{i}\right)
=\sum\limits_{i=0}^{k}p_{i}\phi\left(  X\right)  ^{i}$ (since $\phi$ is an
$F$-algebra homomorphism)
$=\sum\limits_{i=0}^{k}p_{i}S^{i}$ (since $\phi\left(  X\right)  =S$).
But the definition of the $F\left[  X\right]  $-module structure on
$F^{\infty}$ shows that
$P\mathbf{a}=\underbrace{\phi\left(  P\right)  }_{=\sum\limits_{i=0}^{k}
p_{i}S^{i}}\mathbf{a}=\sum\limits_{i=0}^{k}p_{i}\underbrace{S^{i}\mathbf{a}
}_{\substack{=\left(  a_{0+i},a_{1+i},a_{2+i},\ldots\right)  \\\text{(by
\eqref{2})}}}$
$=\sum\limits_{i=0}^{k}p_{i}\left(  a_{0+i},a_{1+i},a_{2+i},\ldots\right)
=\left(  \sum\limits_{i=0}^{k}p_{i}a_{0+i},\sum\limits_{i=0}^{k}p_{i}
a_{1+i},\sum\limits_{i=0}^{k}p_{i}a_{2+i},\ldots\right)  $.
This proves Proposition 2.

Corollary 3. Let $P\in F\left[  X\right]  $ be a polynomial. Let
  $\mathbf{a}\in F^{\infty}$ be a sequence. Then, $\mathbf{a}$ is $P$-linearly
  recursive if and only if $P\mathbf{a}=0$.

Proof of Corollary 3. Write $P$ in the form $P=\sum\limits_{i=0}^{k}
p_{i}X^{i}$ for some $k\in\mathbb{N}$ and some $p_{0},p_{1},\ldots,p_{k}\in
F$. Write the sequence $\mathbf{a}\in F^{\infty}$ in the form $\mathbf{a}
=\left(  a_{0},a_{1},a_{2},\ldots\right)  $. Thus, Proposition 2 yields
$P\mathbf{a}=\left(  \sum\limits_{i=0}^{k}p_{i}a_{0+i},\sum\limits_{i=0}
^{k}p_{i}a_{1+i},\sum\limits_{i=0}^{k}p_{i}a_{2+i},\ldots\right)  $. Hence, we
have the following chain of equivalences:
$\left(  P\mathbf{a}=0\right)  $
$\Longleftrightarrow\ \left(  \left(  \sum\limits_{i=0}^{k}p_{i}a_{0+i}
,\sum\limits_{i=0}^{k}p_{i}a_{1+i},\sum\limits_{i=0}^{k}p_{i}a_{2+i}
,\ldots\right)  =0\right)  $
$\Longleftrightarrow\ \left(  \text{each }n\in\mathbb{N}\text{ satisfies }
\sum\limits_{i=0}^{k}p_{i}a_{n+i}=0\right)  $
$\Longleftrightarrow\ \left(  \mathbf{a}\text{ is }P\text{-linearly
recursive}\right)  $
(by the definition of "$P$-linearly recursive"). This proves Corollary 3.
Proof of Theorem 1. Since $F\left[  X\right]  $ is a principal ideal domain,
Bezout's identity
shows that there are two polynomials $U\in F\left[  X\right]  $ and
$V\in F\left[  X\right]  $ such that $PU+QV=\gcd\left(  P,Q\right)  $.
Consider these $U$ and $V$. Thus, $PU+QV=\gcd\left(  P,Q\right)  =1$ (since
$P$ and $Q$ are coprime).
Corollary 3 (applied to $PQ$ instead of $P$) shows that $\mathbf{a}$ is
$PQ$-linearly recursive if and only if $PQ\mathbf{a}=0$. Hence, $PQ\mathbf{a}
=0$ (since $\mathbf{a}$ is $PQ$-linearly recursive).
The sequence $PU\mathbf{a}\in F^{\infty}$ satisfies $Q\left(  PU\mathbf{a}
\right)  =\underbrace{QPU}_{=UPQ}\mathbf{a}=U\underbrace{PQ\mathbf{a}}_{=0}
=0$. But Corollary 3 (applied to $Q$ and $PU\mathbf{a}$ instead of $P$ and
$\mathbf{a}$) shows that $PU\mathbf{a}$ is $Q$-linearly recursive if and only
if $Q\left(  PU\mathbf{a}\right)  =0$. Thus, $PU\mathbf{a}$ is $Q$-linearly
recursive (since $Q\left(  PU\mathbf{a}\right)  =0$).
The sequence $QV\mathbf{a}\in F^{\infty}$ satisfies $P\left(  QV\mathbf{a}
\right)  =\underbrace{PQV}_{=VPQ}\mathbf{a}=V\underbrace{PQ\mathbf{a}}_{=0}
=0$. But Corollary 3 (applied to $QV\mathbf{a}$ instead of $\mathbf{a}$) shows
that $QV\mathbf{a}$ is $P$-linearly recursive if and only if $P\left(
QV\mathbf{a}\right)  =0$. Thus, $QV\mathbf{a}$ is $P$-linearly recursive
(since $P\left(  QV\mathbf{a}\right)  =0$).
Now, $PU\mathbf{a}+QV\mathbf{a}=\underbrace{\left(  PU+QV\right)  }
_{=1}\mathbf{a}=\mathbf{a}$. Hence, $\mathbf{a}=PU\mathbf{a}+QV\mathbf{a}
=QV\mathbf{a}+PU\mathbf{a}$ is the sum of a $P$-linearly recursive sequence
(namely, $QV\mathbf{a}$) with a $Q$-linearly recursive sequence (namely,
$PU\mathbf{a}$). This proves Theorem 1.
Notice that Theorem 1 gives an alternative approach to explicit formulas for
linearly recursive sequences (like the Binet formula for Fibonacci numbers).
Indeed, repeated application of Theorem 1 yields the following corollary:

Corollary 4. Let $P\in F\left[  X\right]  $ be a monic polynomial. Let
  $P=\prod\limits_{i=1}^{k}P_{i}^{m_{i}}$ be the factorization of $P$ into monic
  irreducible polynomials (with $P_{1},P_{2},\ldots,P_{k}$ being distinct monic
  irreducible polynomials, and $m_{1},m_{2},\ldots,m_{k}$ being nonnegative
  integers). Let $\mathbf{a}\in F^{\infty}$ be a $P$-linearly recursive
  sequence. Then, $\mathbf{a}$ can be written in the form $\mathbf{a}
=\mathbf{a}_{1}+\mathbf{a}_{2}+\cdots+\mathbf{a}_{k}$, where each
  $\mathbf{a}_{i}$ is a $P_{i}^{m_{i}}$-linearly recursive sequence.

For example, if $F=\mathbb{C}$ and $P=X^{2}-X-1$, then we can apply Corollary
4 to any $P$-linearly recursive sequence (setting $k=2$, $P_{1}=X-\dfrac
{1+\sqrt{5}}{2}$, $m_{1}=1$, $P_{2}=X-\dfrac{1-\sqrt{5}}{2}$, and $m_{2}=1$).
We thus conclude that each $\left(  X^{2}-X-1\right)  $-linearly recursive
sequence can be written as the sum of an $\left(  X-\dfrac{1+\sqrt{5}}
{2}\right)  $-linearly recursive sequence (i.e., a geometric sequence with
ratio $\dfrac{1+\sqrt{5}}{2}$) with an $\left(  X-\dfrac{1-\sqrt{5}}
{2}\right)  $-linearly recursive sequence (i.e., a geometric sequence with
ratio $\dfrac{1-\sqrt{5}}{2}$). This lets you easily prove the Binet formula
for Fibonacci sequence. In general, you might have to work harder
(particularly if $P$ is not squarefree, and so some of the $m_{i}$ are $>1$).
Notice also that Theorem 1 does not hold if we forget to require that $P$ and
$Q$ be coprime. For example, the sequence $\left(  0,1,2,\ldots\right)  $ is
always $\left(  X-1\right)  ^{2}$-linearly recursive, but cannot be written as
a sum of two $\left(  X-1\right)  $-linearly recursive sequences. (In fact,
the $\left(  X-1\right)  ^{2}$-linearly recursive sequences are the arithmetic
sequences, while the $\left(  X-1\right)  $-linearly recursive sequences are
the constant sequences.) There is a counterexample for every
pair $\left(  P,Q\right)  $ of non-coprime polynomials $P$ and $Q$ (over any field $F$).
