For all $n\ge 1$, why do there exist integers $a_{i,n}$, $0\le i\le n+1$, not all zero, so that $$a_{0,n} (F_k)^n + a_{1,n} (F_{k-1})^n +\cdots + a_{n,n} (F_{k-n})^n+a_{n+1,n}(F_{k-n-1})^n = 0$$ for all positive integers $k>n+1$, where $F_k$ is the $k^\text{th}$ Fibonacci number? For instance, when $n=1, F_k - F_{k-1} - F_{k-2} = 0,$ meaning we can say $a_{0,1}=+1$, $a_{1,1}=-1$, $a_{2,1}=-1$.
Let $[n,k] := |a_{k,n}|$ denote the $(n,k)^\text{th}$ fibonomial. Prove that $$[n,k] = \dfrac{F_{n+1}^{!}}{F_{n+1-k}^{!} F_k^{!}}$$ for all $n > 0, 0\leq k\leq n+1,$ where $F_i^{!} := 1$ if $i=0$ and $F_1\cdots F_i$ otherwise.
I think an inductive approach can be used for the first proof. It seems one can solve a system of equations by expressing each term $F_i$ for $i>k-n+1$ in terms of $F_{k-n}$ and $F_{k-n+1}$. But I'm not sure why the system is solvable.
And as for the second proof, of the "Fibonomial identity", it looks very similar to the identity for binomial coefficients, but determining $[n,k]$ seems much more computationally intensive.
I will use the notation $$\newcommand{\fbinom}[2]{\binom{#1}{#2}_F}\fbinom{n}k\stackrel{\text{def}}=\frac{F_n^!}{F_k^!F_{n-k}^!}$$ Note that this satisfies the so-called "absorption identity:" $$ \fbinom{n}k=\frac{F_n}{F_k}\fbinom{n-1}{k-1}.\tag0 $$
This was problem $1.2.8-30$ in The Art of Computer Programming vol. 1, by Knuth et al. Specifically, the problem was to give a proof of $$ \sum_{k=0}^m \fbinom mk (-1)^{\lceil (m-k)/2\rceil}(F_{n+k})^{m-1}=0,\tag1 $$ for any $m\ge 1$. The difficulty level given for this problem is [M38], which is on the harder end of problems in that book. Here is the solution given in the back of the book.
We prove this by induction on $m$. This is obvious in the case where $m=1$.
The $k^\text{th}$ summand in the LHS of $(1)$ has $m-1$ copies of $F_{n+k}$. We will take one of these copies, and replace it using the identity $F_{n+k}=F_nF_{k-1}+F_{n+1}F_{k}$. We can then split this into two summations as follows: $$ F_{n+1}\sum_{k=0}^m \fbinom mk (-1)^{\lceil (m-k)/2\rceil}(F_{n+k})^{m-2}F_k+ F_n\sum_{k=0}^m \fbinom mk (-1)^{\lceil (m-k)/2\rceil}(F_{n+k})^{m-2}F_{k-1}\tag2 $$ Let us tackle the left summation first. Using the absorption identity, $(0)$, and then applying the induction hypothesis, $$ \begin{align} F_{n+1}\sum_{k=0}^m \fbinom mk (-1)^{\lceil (m-k)/2\rceil}(F_{n+k})^{m-2}F_k &=F_{n+1}F_m\sum_{k=0}^m \fbinom {m-1}{k-1} (-1)^{\lceil (m-k)/2\rceil}(F_{n+k})^{m-2} \\&=0.\tag3 \end{align} $$ To prove that the second summation is also zero, we use the following Fibonacci identity: $$ (-1)^kF_{m-k}=F_{k-1}F_m-F_kF_{m-1} $$ Namely, we will replace $F_{k-1}$ with $\frac{1}{F_m}((-1)^k F_{m-k}+F_kF_{m-1})$ in the rightmost summation (note that $F_m>0$, so this is allowed). Doing so, we obtain $$ \frac{F_n}{F_m}\sum_{k=0}^m \fbinom mk (-1)^{\lceil (m-k)/2\rceil}(F_{n+k})^{m-2}\cdot (-1)^k F_{m-k} +\frac{F_n F_{m-1}}{F_m}\sum_{k=0}^m \fbinom mk (-1)^{\lceil (m-k)/2\rceil}(F_{n+k})^{m-2}\cdot F_k $$ The rightmost summation above is equal to zero, for the same reason as in $(3)$. For the summation on the left, we ignore the $\frac{F_n}{F_m}$ out front, and reason as follows: \begin{align} \sum_{k=0}^m \fbinom mk (-1)^{\lceil (m-k)/2\rceil}(F_{n+k})^{m-2}(-1)^k F_{m-k} &= \sum_{k=0}^m \fbinom m{m-k} (-1)^{\lceil (m-k)/2\rceil}(-1)^k(F_{n+k})^{m-2} F_{m-k} \\&= (-1)^m F_m\sum_{k=0}^m \fbinom {m-1}{m-k-1} (-1)^{\lceil (m-1-k)/2\rceil}(F_{n+k})^{m-2} \\&= (-1)^m F_m\sum_{k=0}^m \fbinom {m-1}{k} (-1)^{\lceil (m-1-k)/2\rceil}(F_{n+k})^{m-2} \\&= 0. \end{align} Above, we used the absorption identity, the induction hypothesis, and the numerical fact that $(-1)^{\lceil(m-k)/2\rceil}(-1)^k=(-1)^{\lceil (m-1-k)/2\rceil}(-1)^m$. I leave proving this last fact to you.