Results 1 to 4 of 4

Thread: Recurrence relation

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    5

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

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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)$?
    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 $\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.
    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 $\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!
    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: Oct 15th 2011, 11:27 PM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Oct 18th 2010, 02:15 AM
  3. Recurrence Relation Q
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 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: Apr 15th 2009, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum