Thread: 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!