Library · Short Excursions · Combinatorics and games

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.

Revised PDF handout Report an error

Count the bit strings of length nn with exactly one pair of consecutive ones. The convolution ∑FiFn−i\sum F_i F_{n-i} equals the coefficient of xn−2x^{n-2} in 1/(1−x−x2)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)=n−15Ln+25Fn−1f(n) = \tfrac{n-1}{5} L_n + \tfrac{2}{5} F_{n-1}. Full derivation and computational verification in the PDF.

Report an error on this page

Reports are stored by Netlify. See the privacy note.