
Recurrence relation
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 :)

Yo.
I found too.
For the second question, can you do an inductive proof using, for , and ?

I was trying to do it the past 2 hours, and got a solution, but I'm not very convinced about it.
Here is what I did :
1) We have H(0) = 3 which is divisable by 3
2) We have H(1) = 3 which is divisable by 3, too
3) Let's have which is the equivalance relation
 divisable by 3
 divisable by 3
 divisable by 3
So H(2) is divisable by 3 too, and since we have a recurrence relation, this applies to all positive integers following the relation.

Well what we want to prove is that for every .
We know it's true for and . Now, let be an integer, and assume that and are divisible by .
We want to prove that also divides .
So the question is: Is a sum of integers divisible by divisible by ?
If yes, the your proof is complete!