Printable View
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.
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).
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$.
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.
