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}.$$