Is this case of a generalised partition equivalent to Fibonacci numbers?

Question

Let $k=m+\sum^{m+1}_{j=1} a_j$ such that $a,m,k\in\mathbb{N}$ and $a_1$ or $a_{m+1}\geq 0$ with all other $a\geq1$. Note that we assume natural numbers start from $0$ and we have the restriction that $\sum^{m+1}_{j=1} a_j\geq m-1$. Why do there exist $F_{k+2}$ solution sets for values of $m$ and $a_\zeta$, $\forall1\leq\zeta\leq m$? How would this be proven?

For example, when $k=4$, we have $8$ solution sets, \begin{equation} \begin{split} \{m,A\}&=\{0,\{4\}\},\\ &=\{1,\{3,0\}\},\\ &=\{1,\{0,3\}\},\\ &=\{1,\{1,2\}\},\\ &=\{1,\{2,1\}\},\\ &=\{2,\{0,1,1\}\},\\ &=\{2,\{1,1,0\}\},\\ &=\{2,\{0,2,0\}\},\\ \end{split} \end{equation} where $A=\bigcup^{m+1}_{j=1} a_j$. Note that $\{2,\{1,0,1\}\}$ is invalid since only the first or final $a$'s may be $0$. Also, $\{3,\{0,1,0\}\}$ is invalid since $\sum^{m+1}_{j=1} a_j\geq m-1$.

Any help would be much appreciated.

Update: Let $b_j=a_j-1$ for $1<j<m+1$ and $b_j=a_j$ when $j=1$ or $j=m+1$: $$k=2m-1+\sum _{j=1}^{m+1}b_j.$$ Hence, for fixed $m$, there exist $$\binom{k-2m+1+m+1-1}{m+1-1}=\binom{k-m+1}{m},$$ solutions for $k-2m+1=b_1+\cdots +b_{m+1}$. Summing over $m$ yields $$F_{k+2}=\sum _{m=0}^{k+1}\binom{k+1-m}{m}.$$

Answer 1

Without mistake on my behalf, a proof can be given as follows:

Denote the set of all solutions (for a given value of $k$) by $\mathcal F_k$. Every element of $\mathcal F_k$ ending with a last coefficient $\geq 1$ corresponds to an element of $\mathcal F_{k-1}$ after decreasing its last element (of the corresponding sequence $(a_1,\ldots)$) by $1$. Elements of $\mathcal F_k$ ending with a last coefficient $0$ correspond similarly to elements of $\mathcal F_{k-2}$: Remove the last coefficient and decrease the (originally second-last) remaining last coefficient by $1$. This proves the result by induction after checking the initial conditions.