The problem:

Define the recurrence relation by the rules :
for . Calculate . Prove by induction that is divisible by 3 for all (n - positive integer).


I calculate using simple algebra and get (I will be grateful if you can check that, so I didn't miss anything). But I'm stuck on the proving by induction part. I need to show somehow that sum of the digits of the number are divisble by 3, but I don't know how to do it. I will appreciate any ideas or solutions, thank you