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

  • 2
    $\begingroup$ 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/… $\endgroup$
    – user44191
    Jul 11, 2021 at 15:53
  • $\begingroup$ @user44191 Thank you very much! Yes, I was too caught up in notation to realise. $\endgroup$
    – UNOwen
    Jul 11, 2021 at 16:42

1 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.

  • $\begingroup$ Thank you for your reply. I like your method as it seems more elegant than mine. $\endgroup$
    – UNOwen
    Jul 11, 2021 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.