Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By SlipEternal
  • 1 Post By SlipEternal

Math Help - recurrence relation

  1. #1
    Newbie
    Joined
    May 2013
    From
    Canada
    Posts
    10

    recurrence relation

    recurrence relation-qq-20131014193648.jpg

    I notice that n must be even, thus we have
    f(2)= 2
    f(4)= 4
    f(6)= 8
    f(8)= 16

    so every time we add a 3 by 2 grid , it doubled.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,836
    Thanks
    706

    Re: recurrence relation

    \begin{align*}f(0) & = 1 \\ f(1) & = 0 \\ f(2) & = 2 \\ f(3) & = 0 \\ f(4) & = 4 \\ f(5) & = 0 \\ f(6) & = 8 \\ f(7) & = 0 \\ f(8) & = 16\end{align*}

    \forall n\ge 0, f(n+2) = 2f(n)

    Note: The characteristic polynomial is x^2-2, so the roots are \pm\sqrt{2}. Hence f(n) = A(\sqrt{2})^n + B(-\sqrt{2})^n. Then 1 = A+B and 0 = A\sqrt{2} - B\sqrt{2}, so solving the system of equations, we have A = 1-B and 0 = (1-2B)\sqrt{2}, so A = B = \dfrac{1}{2}. Hence f(n) = \dfrac{\left(\sqrt{2}\right)^n + \left(-\sqrt{2}\right)^n}{2}
    Last edited by SlipEternal; October 14th 2013 at 05:15 PM.
    Thanks from hezhiweitian
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2013
    From
    Canada
    Posts
    10

    Re: recurrence relation

    Quote Originally Posted by SlipEternal View Post
    \begin{align*}f(0) & = 1 \\ f(1) & = 0 \\ f(2) & = 2 \\ f(3) & = 0 \\ f(4) & = 4 \\ f(5) & = 0 \\ f(6) & = 8 \\ f(7) & = 0 \\ f(8) & = 16\end{align*}

    \forall n\ge 0, f(n+2) = 2f(n)

    Note: The characteristic polynomial is x^2-2, so the roots are \pm\sqrt{2}. Hence f(n) = A(\sqrt{2})^n + B(-\sqrt{2})^n. Then 1 = A+B and 0 = A\sqrt{2} - B\sqrt{2}, so solving the system of equations, we have A = 1-B and 0 = (1-2B)\sqrt{2}, so A = B = \dfrac{1}{2}. Hence f(n) = \dfrac{\left(\sqrt{2}\right)^n + \left(-\sqrt{2}\right)^n}{2}
    I notice that you answered my previous thread too and I'm really appreciated.However, your work seems beyond the method my professor have taught me or a completely different approach. For this one , everything just seems "MAGICAL" to me.
    Last edited by hezhiweitian; October 14th 2013 at 05:42 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,836
    Thanks
    706

    Re: recurrence relation

    Given a recurrence relation of the form f(n+k) = a_0 f(n) + a_1 f(n+1) + \ldots + a_{k-1}f(n+k-1), its characteristic polynomial is x^k = a_0x^0 + a_1x^1 + \ldots + a_{k-1}x^{k-1}. Let \alpha_1, \ldots, \alpha_k be the roots of that characteristic polynomial. If the roots are all distinct, then f(n) = \sum_{i = 1}^k A_i(\alpha_i)^n. If the roots are not distinct, the formula is a bit more complex, and not necessary for this problem. The proof of this requires differential equations, but the process is frequently taught without proof in discrete mathematics classes.

    To solve for A_i, you plug in the initial values f(0) = \sum_{i = 1}^k A_i(\alpha_i)^0 = \sum_{i = 1}^k A_i. f(1) = \sum_{i = 1}^k A_i(\alpha_i)^1 = \sum_{i = 1}^k A_i\alpha_i. Etc.

    So, in this case, I used the characteristic polynomial to find f(n) = A(\sqrt{2})^n + B(-\sqrt{2})^n. Plugging in f(0)=1=A(\sqrt{2})^0+B(-\sqrt{2})^0 = A+B and f(1)=0=A(\sqrt{2})^1 + B(-\sqrt{2})^1 = (A-B)\sqrt{2}. This gave me a system of two equations in two variables. I solved for A and B, and plugged them in.
    Last edited by SlipEternal; October 14th 2013 at 06:17 PM.
    Thanks from hezhiweitian
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relation
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: May 24th 2010, 03:04 AM
  2. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 22nd 2010, 05:14 AM
  3. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 23rd 2010, 12:06 PM
  4. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 22nd 2009, 09:46 AM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 08:02 AM

Search Tags


/mathhelpforum @mathhelpforum