a[n+1]+a[n]は整数とわかる前提があると思います

そのもとでは、9( a[n+1]+a[n] )は
「9×(整数)」の形なので、9の倍数です

よって、a[n+3] = (9の倍数) + a[n]です
この式から、
a[n]が9の倍数なら、
a[n+3] = (9の倍数) + (9の倍数)なので、
a[n+3]は9の倍数です

a[n]が9の倍数でない（余りr）なら
a[n] = (9の倍数) +rであり、
a[n+3] = (9の倍数) + (9の倍数) +rなので、
a[n+3]は9で割ってr余ります

すなわち、a[n+3]とa[n]とで、
それぞれ9で割った余りは一致します