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

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

• Your last equation is a well-known result, that the Fibonacci numbers appear when summing in Pascal's triangle "along a diagonal". Consider e.g. maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/… Jul 11, 2021 at 15:53
• @user44191 Thank you very much! Yes, I was too caught up in notation to realise. Jul 11, 2021 at 16:42

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.