Results 1 to 4 of 4

Math Help - Entering recurrence relation into wolframalpha

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,859
    Thanks
    722

    Entering recurrence relation into wolframalpha

    I am trying to figure out if there is a closed form for this function:

    f:\Bbb{Z} \to \Bbb{Z}

    defined by

    f(n) = \begin{cases}0 & n<0 \\ n+1+f(n-2)+f(n-6)+f(n-18)+f(n-54) & \text{otherwise} \end{cases}

    It should look something like a sum or product of binomial coefficients (I think). I found the Piecewise mathematica function, but I don't know how to tell wolframalpha that it is a recurrence relation.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,859
    Thanks
    722

    Re: Entering recurrence relation into wolframalpha

    The initial conditions are all negative numbers give zero (similar to how \binom{n}{r} gives zero if r<0). Can I use something like

    Code:
    RSolve[f(n) == n+1+f(n-2)+f(n-6)+f(n-18)+f(n-54) && RecurrenceTable[f(k)=0,{k,-54,-1}], f(n), n]
    ??

    Wolframalpha doesn't understand that formula, though. When I tried a simpler one, it gave me a closed form in terms of a DifferenceRoot, so there may not be any general closed form. What I am hoping to evaluate is:

    f_k(n) = \begin{cases}0 & n<0 \\ n+1+\sum_{i=0}^k f_k(n-2\cdot 3^i) & \text{otherwise}\end{cases}

    Then for each k, I want to know if this limit converges to something nonzero:

    \lim_{n \to \infty} \dfrac{f_k(n-3^{k+1})}{f_k(n)}

    It is a relation I found while examining primitive roots of 3^{k+1}. It seems certain sums can fall seemingly arbitrarily in a relatively fixed range, and I want to know if it matters if I am off by a couple powers of 3 when taking the limit of that function over another function (as n approaches infinity).
    Last edited by SlipEternal; May 15th 2014 at 11:14 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,859
    Thanks
    722

    Re: Entering recurrence relation into wolframalpha

    Seems like generating functions might be the way to go.

    g_k(x) = \dfrac{1}{\displaystyle (1-x)^2\left(1-\sum_{n=0}^k x^{2\cdot 3^n} \right) }

    is the generating function for f_k(n) where g_k(x) = \sum_{n\ge 0} f_k(n)x^n.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,859
    Thanks
    722

    Re: Entering recurrence relation into wolframalpha

    For anyone who is interested, this turned out to be much simpler than I expected. If k>0, let r_k be the root of 1-\sum_{n=0}^k x^{2\cdot 3^n} with smallest magnitude (in the complex plane). It turns out that these polynomials always seem to have exactly two real roots, and the real roots have the smallest magnitude. Then, the limit I was interested in:

    \lim_{n \to \infty} \dfrac{f_k(n-t)}{f_k(n)} = r_k^t for any positive integer t.

    Just thought it was kinda cool that it wound up with such a simple answer.
    Last edited by SlipEternal; May 17th 2014 at 08:28 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 29th 2011, 11:24 PM
  2. Help with recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 10th 2010, 04:24 PM
  3. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 13th 2009, 03:37 PM
  4. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 7th 2008, 11:06 PM
  5. Recurrence Relation?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 9th 2008, 04:14 AM

Search Tags


/mathhelpforum @mathhelpforum