gcc already optimises away loops like for (i = 0; i < n; i++) s += i;

It wouldn't be too much of a stretch to detect and optimise away code that computes linearly recurrent sequences.