Entering recurrence relation into wolframalpha

Printable View

May 15th 2014, 09:39 PM
SlipEternal

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.
May 15th 2014, 11:01 PM
SlipEternal

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).
May 16th 2014, 12:20 AM
SlipEternal

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$ .
May 17th 2014, 07:28 AM
SlipEternal

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.