
Recurrence relation
The problem:
Define the recurrence relation $\displaystyle H(n)$ by the rules :
$\displaystyle H(0) = 3 , H(1) = 3, H(n) = 2H(n1)  H(n2) + 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 :)

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

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

Well what we want to prove is that for every $\displaystyle n \in \mathbb{N}, 3H(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(k2)$ and $\displaystyle H(k1)$ are divisible by $\displaystyle 3$.
We want to prove that $\displaystyle 3$ also divides $\displaystyle H(k)$.
$\displaystyle H(k)=2H(k1) + H(k2)  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!