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



Is this case of a generalised partition equivalent to Fibonacci numbers?
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.


