Recurrence relation

cyb3r · #1 $Old$ November 16th, 2008, 07:53 AM

The problem:

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

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

clic-clac · #2 $Old$ November 16th, 2008, 08:54 AM

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

cyb3r · #3 $Old$ November 16th, 2008, 09: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 $H(2)$ which is the equivalance relation $2H(n-1)-H(n-2)+6$

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

clic-clac · #4 $Old$ November 16th, 2008, 10:02 AM

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

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

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

If yes, the your proof is complete!