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.
Best Answer
Yes, this identity is well known. According to Singh's The so-called Fibonacci numbers in ancient and medieval India, 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, 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.