Skip to content
Vamshi Jandhyala

Mathematics

Subsets of {1,…,n} with Exactly One Pair of Consecutive Integers

A generating-function argument in which the count is the convolution of Fibonacci numbers; partial fractions over the golden-ratio roots give a closed form involving Fibonacci and Lucas numbers, with f(10) = 235.

Download PDF →


Count the bit strings of length nn with exactly one pair of consecutive ones. The convolution FiFni\sum F_i F_{n-i} equals the coefficient of xn2x^{n-2} in 1/(1xx2)21/(1-x-x^2)^2; decomposing this by partial fractions over r±=(1±5)/2r_\pm = (1\pm\sqrt 5)/2 yields the closed form f(n)=n15Ln+25Fn1f(n) = \tfrac{n-1}{5} L_n + \tfrac{2}{5} F_{n-1}. Full derivation and computational verification in the PDF.


More mathematical writing →