Consider the recursion g0 = a, g1 = b, gn = gn−1 + gn−2, n = 2, 3, . . . . We compute the Frobenius norm of the r-circulant matrix corresponding to g0, . . . , gn−1. We also give three lower bounds (with equality conditions) for the spectral norm of this matrix. For this purpose, we present three ways to estimate the spectral norm from below in general.