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 :)
Nov 16th 2008, 06:54 AM
I found too.
For the second question, can you do an inductive proof using, for , and ?
Nov 16th 2008, 07:49 AM
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.
Nov 16th 2008, 08:02 AM
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 ?