A bijective proof of Riordan's theorem on powers of Fibonacci numbers (Q1297448)

Let \(F_n\) and \(L_n\) be the \(n\)-th Fibonacci and Lucas numbers, respectively, and define \(F_k(x)=\sum_{n=0}^{\infty}{F_n^kx^n}\). The author proves the following recurrence given by Riordan: \[ (1-L_kx-(-1)^kx^2)F_k(x)=1+kx\sum_{j=1}^{\lfloor k/2 \rfloor} {(-1)^j/ja_{kj}F_{k-2j}((-1)^jx)}. \] This recurrence follows directly from the following relation: \[ F_n^k=L_kF_{n-1}^k-(-1)^kF_{n-2}^k+\delta_{n,0}+ \sum_{m,j \geq 1} b_{mk}\binom m j (-1)^{jn} F_{n-1}^{k-2j}, \] where \[ b_{mk}=k/m {k-m-1\choose m-1}\text{ and }\delta_{n,0}=1\text{ if }n=0,\text{ and }\delta_{n,0}=0\text{ if }n>0. \] Let \(A(n)=\{(a_1, \ldots ,a_r):r \geq 0, a_i \in \{ 1,2 \}, a_1+ \cdots + a_r=n \},\) let \(B(n)=A(n) \cup A(n-2),\) and define \(M_n^k\) and \(N_n^k\) to be \((A(n))^k\) and \((A(n-1))^k \times B(k),\) respectively. The author's proof of the relation above begins with the fact that \(F_n= |A(n)|\) and \(L_n= |B(n)|.\) The author constructs a map \(m_n^k\) from \(N_n^k\) to \(M_n^k\) that extends the bijection, given by Werman and Zeilberger in their proof of Cassini's identity, from \((A(n) \times A(n))-(2,2,\ldots, 2)\) to \((A(n-1) \times A(n+1))-(2,2, \ldots, 2).\) The author is able to establish the relation above by determining the domain, range, and injectivity of \(m_n^k.\)