Solving coupled recursion equations for a target variable

I apologize if this is unhelpful (and it is not efficient):

m = {{1, 0, 1}, {1, 0, 0}, {0, 1, 1}}
d[n_] := MatrixPower[m, n].{a, b, c}.{1, 1, 1}
df = FindSequenceFunction[d /@ Range[10]] /. {a -> 1, b -> 1, c -> 1};

yields a DifferenceRoot.

Testing one instance:

FullSimplify[d[n] - d[n - 1] - d[n - 2] - d[n - 4]]

yields 0.

Obviously, this is only 1 instance but perhaps it prompts better ideas.

Without setting initial conditions. Looking for linear recurrences:

rs = First@RSolve[{
      a[n] == a[n - 1] + c[n - 1],
      b[n] == a[n - 1],
      c[n] == b[n - 1] + c[n - 1],
      a[1] == a1, c[1] == c1, b[1] == b1}, {a@n, b@n, c@n},  n] ;

ss = Simplify[Table[a[n] + b[n] + c[n] /. rs, {n, 0, 9}] // N // Chop] // Chop;
ss1 = ss /. x_Real :> Round[x]
FindLinearRecurrence@ss1

(* {2, -1, 1} *)

So we found a different linear relationship than yours ;)

d[n] == 2 d[n-1] - d[n-2] +  d[n-3]

A general solution, making no assumptions about initial conditions, is as follows. (The derivation proceeds much like the corresponding derivation for a set of first order ODEs.) First, eliminate b.

eqs1 = {a[n] == a[n - 1] + c[n - 1], b[n] == a[n - 1], c[n] == b[n - 1] + c[n - 1]};
bsolv = Solve[d[n] == a[n] + b[n] + c[n], b[n]][[1, 1]];
eqs2 = eqs1 /. {bsolv, (bsolv /. n -> n - 1)};
eqs3 = Equal @@@ First@Solve[eqs2, {a[n], d[n], c[n]}];
(* {a[-1 + n] + c[-1 + n] == a[n], 
    a[-1 + n] + c[-1 + n] + d[-1 + n] == d[n], 
    a[-1 + n] + c[n] == d[-1 + n]} *)

Second, Eliminate a and c.

Eliminate[Join[{eqs3[[2]]}, (eqs3 /. n -> n - 1), (eqs3 /. n -> n - 2)], 
    {a[n - 1], a[n - 2], a[n - 3], c[n - 1], c[n - 2], c[n - 3]}];
ans = Equal @@ Solve[%, d[n]][[1, 1]]
(* d[n] == d[-3 + n] - d[-2 + n] + 2 d[-1 + n] *)

which is the result obtained by Dr. Belisarius by a different approach. As expected, it is a third order difference equation. The expression in the question is obtained by

Equal @@ Solve[(Subtract @@ ans) + (Subtract @@ ans /. n -> n - 1) == 0, d[n]][[1, 1]]

This difference equation is an order higher than necessary and, therefore, has a solution with four arbitrary constants instead of three.

More compact derivation

An alternative, more compact derivation can be achieved by treating all four equations in parallel.

{d[n] == a[n] + b[n] + c[n], a[n] == a[n - 1] + c[n - 1], 
    b[n] == a[n - 1], c[n] == b[n - 1] + c[n - 1]};

Equal @@@ First@Solve[%, {d[n], a[n], b[n], c[n]}];
Eliminate[Join[{First@%}, Flatten@Array[% /. n -> n - # &, 3]], 
    Flatten@Array[{a[n - #], b[n - #], c[n - #]} &, 4]];
Equal @@ Solve[%, d[n]][[1, 1]]

(* d[n] == d[-3 + n] - d[-2 + n] + 2 d[-1 + n] *)