Thread: Entering recurrence relation into wolframalpha

1. Entering recurrence relation into wolframalpha

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

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

defined by

$\displaystyle 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.

2. Re: Entering recurrence relation into wolframalpha

The initial conditions are all negative numbers give zero (similar to how $\displaystyle \binom{n}{r}$ gives zero if $\displaystyle 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:

$\displaystyle 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 $\displaystyle k$, I want to know if this limit converges to something nonzero:

$\displaystyle \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 $\displaystyle 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).

3. Re: Entering recurrence relation into wolframalpha

Seems like generating functions might be the way to go.

$\displaystyle 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 $\displaystyle f_k(n)$ where $\displaystyle g_k(x) = \sum_{n\ge 0} f_k(n)x^n$.

4. Re: Entering recurrence relation into wolframalpha

For anyone who is interested, this turned out to be much simpler than I expected. If $\displaystyle k>0$, let $\displaystyle r_k$ be the root of $\displaystyle 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:

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

Just thought it was kinda cool that it wound up with such a simple answer.