A *Fibonacci-type sequence* is a sequence with two seed-values, $F\_1$ and $F\_2$, and which, for all $n>2$, abides by the recurrence relation $F\_n = F\_{n-1} + F\_{n-2}$. If $F\_1 = F\_2 = s$, then the $n$th number is equal to the number of compositions of $n-1$, consisting only of $1$'s and $2$'s, multiplied by $s$:


$$\begin{align} F\_n = \sum\_{k=0}^{\lfloor (n-1)/2\rfloor} \binom{\lfloor (n-1)/2\rfloor+k}{2k+1} s \end{align} $$


I also have a similar kind of formula for when $F\_1 \ne F\_2$ that uses the exact same technique (counting compositions that is), though I chose not include it here for brevity's sake.


So, my question is the following; **has this result been found before?** I know that people know about the link between compositions of $n-1$ and the $n$th Fibonacci number (it's mentioned on Wikipedia), but have people found this formula? I would think so, but I haven't found it when Googling.


**NB:** If you have $F\_0 = 0$, that amounts to $F\_1 = F\_2$, which means the above formula still stands even though, technically, the seed-values aren't equal.



Explicit formula for Fibonacci numbers; compositions of $n$
Yes, this identity is well known. According to Singh's [The so-called Fibonacci numbers in ancient and medieval India](https://www.sciencedirect.com/science/article/pii/0315086085900217), the $s=1$ case has been known since at least the the 14th century. Since everything in the sequence with $F\_1 = F\_2 = s$ is a multiple of $s$, the formula for that case follows immediately.


Your Fibonacci-type sequence is known in the literature as generalized Fibonacci sequences or, in Art Benjamin & Jenny Quinn's wonderful book [*Proofs that Really Count*](https://bookstore.ams.org/dol-27/), Gibonacci numbers. Their Identity 4 is the $s=1$ case of your formula, proven combinatorially with square and domino tilings, equivalently compositions restricted to parts 1 and 2 (an interpretation Singh suggests was known some time BCE). With $F\_1 = F\_2 = s$, the parts are restricted to $s$ and $2s$ analogously.


