Of fibonomials, pellonomials, and tribonomials, etc I. Linear recurrence with order 2
Given the Fibonacci numbers $F_n$, we have 
$$\begin{aligned}
&F_n+F_{n+1}-F_{n+2}=0\\[1mm]
&F_n^2-2F_{n+1}^2-2F_{n+2}^2+F_{n+3}^2=0\\[1mm]
&F_n^3+3F_{n+1}^3-6F_{n+2}^3-3F_{n+3}^3+F_{n+4}^3=0\\
&\small\text{and so on.}
\end{aligned}$$
The coefficients are called fibonomials. (The version for the Pell numbers are quaintly called the pellonomials.) 
II. Linear recurrence with order 3
For the tribonacci numbers $T_n$, we have,
$$\begin{aligned}
&T_n+T_{n+1}+T_{n+2}-T_{n+\color{brown}3}=0\\[1mm]
&T_n^2 - T_{n + 2}^2 + 6T_{n + 3}^2 - 3T_{n + 4}^2 - 2T_{n + 5}^2 + T_{n + \color{brown}6}^2 = 0\\[1mm]
&T_n^3 - 2T_{n + 1}^3 + 2T_{n + 2}^3 - T_{n + 3}^3 - 14T_{n + 4}^3 \;\;+\;\; \dots \;\;+\;\; T_{n + \color{brown}{10}}^3 = 0\\
\end{aligned}$$
Notice that $3,6,10$ (and next is $15$) are generated by $m=\tfrac{1}{2}(k+1)(k+2)$.

III. Question: 
Given a linear recurrence of order $d$,
$$s_n = a_1s_{n-1}+a_2s_{n-2}+\dots+a_ds_{n-d}$$
with $a_d\neq0$. Assume one can find a formula valid for all positive integer $n$,
$$c_0s_n^k+c_1s_{n+1}^k+c_2s_{n+2}^k+\dots+c_{m}s_{n+m}^k=0$$
with integer $c_i$ and positive integer $k$. How do we show that the required $m$ is a function of $k$ (and $d$) and in fact is a figurate number? Hence,
$$\begin{array}{|c|c|c|}
\hline
\text{Order}\; d&m&\text{Name}\\
\hline
2&k+1&\text{linear}\\
\hline
3&\tfrac{1}{2}(k+1)(k+2)&\text{triangular numbers}\\
\hline
4&\tfrac{1}{6}(k+1)(k+2)(k+3)&\text{tetrahedral numbers}\\
\hline
\end{array}$$

P.S. I tested it with the Padovan sequence $P_n = 1, 1, 1, 2, 2, 3, 4, 5, 7, 9,\dots$ (and others with 3rd order) and it has the same pattern,
$$\begin{aligned}
&P_n+P_{n+1}-P_{n+\color{brown}3}=0\\[1mm]
&P_n^2 - P_{n + 1}^2 + P_{n + 2}^2 - P_{n + 3}^2 - P_{n + 4}^2 - P_{n + 5}^2 + P_{n + \color{brown}6}^2 = 0\\
\end{aligned}$$
and so on. I also tested the tetranacci sequence and for $k = 1,2,3$ we have $m=4,10,20$ which are the first tetrahedral numbers. 
 A: Caveat: this is more a sketch of a possible approach than a complete answer.
Given a general linear recurrence $x_n = a_1 x_{n-1} + \ldots + a_r x_{n-r}$ the solution is typically of the form $x_n = \alpha_1 \beta_1{}^n + \ldots + \alpha_r \beta_r{}^n$.
So if we consider $$x_n^k = (\alpha_1 \beta_1{}^n + \ldots + \alpha_r \beta_r{}^n)^k = \sum_{\lambda \,\vdash\, k} A_\lambda \left(\beta_1{}^{\lambda_1}\ldots \beta_r{}^{\lambda_r}\right)^n$$(where $\lambda \,\vdash\, k$ means that $\lambda$ is a partition of $k$, and the formulation of $A_\lambda$ in terms of the $\alpha_i$ is left as an exercise) we see that we can expect it to satisfy a linear recurrence.
Gaps in the argument:


*

*I haven't covered the case where the characteristic polynomial of the original recurrence has repeated roots. I think this gap can be filled because that gives terms $\alpha_i x^j \beta_i^x$ which carry through to give similar terms in the new recurrence.

*I haven't argued for the order of the derived recurrence.

A: Here's a way of phrasing Peter's proof that I think makes it less bookkeeping-intensive:


*

*Define the Hadamard product of two sequences $\{a_n\}$, $\{b_n\}$ to be the sequence $\{a_n b_n\}$.

*Note that the vector space of sequences forms an algebra under Hadamard product (that is, it distributes over ordinary addition and is compatible with ordinary scalar multiplication).

*Call a sequence simple if it is of the form $\{n^k \alpha^n\}$ for some constants $k,\alpha$.

*Note that the Hadamard product of simple sequences is simple.

*Note that a sequence is the solution to a constant-coefficient linear recurrence relation if and only if it is a linear combination of simple sequences.

*Conclude that the Hadamard product of two such solutions is also the solution to a constant-coefficient linear recurrence relation.

*Induct!


Alternately, see these notes for another perspective...
