(Colorful Checkerboards) A colorful skinny checkerboard of length n is a 1 x n board, where each square is colored either red or blue. Find a closed form formula for the number of colorful skinny checkerboards of length n in which no two adjacent squares are both colored blue. Verify that your formula is correct with a proof.

I need the exact formula, it will be great if you prove it by induction.

thanks