Results 1 to 4 of 4

Math Help - Recurrence relation

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    5

    Recurrence relation

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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)?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    5
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 15th 2011, 11:27 PM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 02:15 AM
  3. Recurrence Relation Q
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 30th 2009, 11:57 PM
  4. Recurrence Relation HELP
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2009, 01:18 PM
  5. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum