1. ## Recurrence relation

The problem:

Define the recurrence relation $\displaystyle H(n)$ by the rules :
$\displaystyle H(0) = 3 , H(1) = -3, H(n) = 2H(n-1) - H(n-2) + 6$ for $\displaystyle n>=2$. Calculate $\displaystyle H(6)$. Prove by induction that $\displaystyle H(n)$ is divisible by 3 for all $\displaystyle n$ (n - positive integer).

I calculate $\displaystyle H(6)$ using simple algebra and get $\displaystyle H(6) = 57$ (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 $\displaystyle H(n)$ are divisble by 3, but I don't know how to do it. I will appreciate any ideas or solutions, thank you

2. Yo.
I found $\displaystyle 57$ too.
For the second question, can you do an inductive proof using, for $\displaystyle n \geq 2$, $\displaystyle H(n-1)$ and $\displaystyle H(n-2)$?

3. 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 $\displaystyle H(2)$ which is the equivalance relation $\displaystyle 2H(n-1)-H(n-2)+6$

$\displaystyle 2H(n-1) = H(1)$ - divisable by 3
$\displaystyle H(n-2) = H(0)$ - divisable by 3
$\displaystyle 6 = 6$ - 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.

4. Well what we want to prove is that for every $\displaystyle n \in \mathbb{N}, 3|H(n)$.
We know it's true for $\displaystyle H(0)$ and $\displaystyle H(1)$. Now, let $\displaystyle k\geq 2$ be an integer, and assume that $\displaystyle H(k-2)$ and $\displaystyle H(k-1)$ are divisible by $\displaystyle 3$.
We want to prove that $\displaystyle 3$ also divides $\displaystyle H(k)$.

$\displaystyle H(k)=2H(k-1) + H(k-2) - 6$

So the question is: Is a sum of integers divisible by $\displaystyle 3$ divisible by $\displaystyle 3$?

If yes, the your proof is complete!